Pseudorandom Generators for Regular Branching Programs

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.

Authors

• Mark Braverman
• Anup Rao 0001
• Ran Raz
• Amir Yehudayoff

Keywords

• Generators
• Games
• Computational modeling
• Electronic mail
• Labeling
• Equations
• Random variables
• Pseudo-random
• Regular Branching
• Branching Program
• Loss Of Generality
• Program Evaluation
• Random Walk
• Middle Layer
• Edge Weights
• Final Layer
• Sum Of Terms
• Child Nodes
• Biased Distribution
• Total Gain
• Distribution Of Nodes
• Power-of-two
• Induction Hypothesis
• Random Bits
• Input Bits
• Pseudorandomness
• branching programs
• explicit constructions