ECCC-Report TR10-035https://eccc.weizmann.ac.il/report/2010/035Comments and Revisions published for TR10-035en-usSun, 07 Mar 2010 22:47:15 +0200
Paper TR10-035
| Pseudorandom Generators for Regular Branching Programs |
Mark Braverman,
Anup Rao,
Ran Raz,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2010/035We 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$.Sun, 07 Mar 2010 22:47:15 +0200https://eccc.weizmann.ac.il/report/2010/035