ECCC-Report TR11-117https://eccc.weizmann.ac.il/report/2011/117Comments and Revisions published for TR11-117en-usSat, 10 Sep 2011 23:12:34 +0300
Paper TR11-117
| Pseudorandomness for read-once formulas |
Andrej Bogdanov,
Periklis Papakonstantinou,
Andrew Wan
https://eccc.weizmann.ac.il/report/2011/117We give an explicit construction of a pseudorandom generator for read-once formulas whose inputs can be read in arbitrary order. For formulas in $n$ inputs and arbitrary gates of fan-in at most $d = O(n/\log n)$, the pseudorandom generator uses $(1 - \Omega(1))n$ bits of randomness and produces an output that looks $2^{-\Omega(n)}$-pseudorandom to all such formulas.
Our analysis is based on the following lemma. Let $P = Mz + e$, where $M$ is the parity-check matrix of a sufficiently good binary error-correcting code of constant rate, $z$ is a random string, $e$ is a small-bias distribution, and all operations are modulo 2. Then for every pair of functions $f, g\colon \{0,1\}^{n/2} \to \{0,1\}$ and every equipartition $(I, J)$ of $[n]$, the distribution $P$ is pseudorandom for the pair $(f(x|_I), g(x|_J))$, where $x|_I$ and $x|_J$ denote the restriction of $x$ to the coordinates in $I$ and $J$, respectively.
More generally, our result applies to read-once branching programs of bounded width with arbitrary ordering of the inputs. We show that such branching programs are more powerful distinguishers than those that read their inputs in sequential order: There exist (explicit) pseudorandom distributions that separate these two types of branching programs.
Sat, 10 Sep 2011 23:12:34 +0300https://eccc.weizmann.ac.il/report/2011/117