Name
Abstract | ||
|---|---|---|
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 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/\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$. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/FOCS.2010.11 | Foundations of Computer Science |
Keywords | DocType | Volume |
pseudorandom generator,general read-once,pseudorandom generators,log n,random string,small width,new pseudorandom generator,regular width,small probability,random input,regular branching programs,branching program,vertex,pseudorandomness,labeling,generators,games,random variables,random number generation,computational modeling | Conference | 43 |
Issue | ISSN | ISBN |
3 | 0272-5428 | 978-1-4244-8525-3 |
Citations | PageRank | References |
28 | 1.06 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Braverman | 1 | 810 | 61.60 |
| Anup Rao | 2 | 581 | 32.80 |
| Ran Raz | 3 | 2772 | 180.87 |
| Amir Yehudayoff | 4 | 530 | 43.83 |