Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



TR11-117 | 3rd September 2011 12:21

Pseudorandomness for read-once formulas


Authors: Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan
Publication: 10th September 2011 23:12
Downloads: 1017


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

ISSN 1433-8092 | Imprint