Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



TR10-035 | 7th March 2010 22:47

Pseudorandom Generators for Regular Branching Programs


Authors: Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff
Publication: 7th March 2010 22:47
Downloads: 1879


We give new pseudorandom generators for \emph{regular} read-once branching programs of small width.
A branching program is regular if the in-degree of every vertex in it is (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/\epsilon))\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 $\epsilon$.

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 $\gamma$ on a uniformly random input, then the error of the generator above is at most $2 \epsilon/\gamma^2$.

ISSN 1433-8092 | Imprint