TR10-035 Authors: Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff

Publication: 7th March 2010 22:47

Downloads: 3726

Keywords:

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$.