@inproceedings{36ab2b29e88447d590d1f33d2684a581,

title = "Pseudorandom generators for regular branching programs",

abstract = "We give new pseudorandom generators for regular read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is either 0 or 2. For every width d and length n, our pseudorandom generator uses a seed of length O((log d + log log n + log(1/ε)) log n) to produce n bits that cannot be distinguished from a uniformly random string by any regular width d length n read-once branching program, except with probability ε. We also give a result for general read-once branching programs, in the case that there are no vertices that are reached with small probability. We show that if a (possibly non-regular) branching program of length n and width d has the property that every vertex in the program is traversed with probability at least γ on a uniformly random input, then the error of the generator above is at most 2ε/γ 2.",

keywords = "Branching programs, Explicit constructions, Pseudorandomness",

author = "Mark Braverman and Anup Rao and Ran Raz and Amir Yehudayoff",

year = "2010",

doi = "10.1109/FOCS.2010.11",

language = "English (US)",

isbn = "9780769542447",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "40--47",

booktitle = "Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010",

address = "United States",

note = "2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 ; Conference date: 23-10-2010 Through 26-10-2010",

}