Pseudorandomness for Read-Once Formulas

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 - Ω(1))n bits of randomness and produces an output that looks 2^-Ω(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: {0,1}^n/2→ {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 / and J, respectively. More generally, our result applies to read-once branching pro- grams 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.