TY - GEN
T1 - Pseudorandom generators for regular branching programs
AU - Braverman, Mark
AU - Rao, Anup
AU - Raz, Ran
AU - Yehudayoff, Amir
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
KW - Branching programs
KW - Explicit constructions
KW - Pseudorandomness
UR - http://www.scopus.com/inward/record.url?scp=78751520954&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78751520954&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2010.11
DO - 10.1109/FOCS.2010.11
M3 - Conference contribution
AN - SCOPUS:78751520954
SN - 9780769542447
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 40
EP - 47
BT - Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
T2 - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
Y2 - 23 October 2010 through 26 October 2010
ER -