Thomas Steinke: Pseudorandomness for Regular Branching Programs via Fourier Analysis

We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is O(log2n), where n is the length of the branching program. The previous best seed length known for this model was n1/2+o(1), which follows as a special case of a generator due to Impagliazzo, Meka, and Zuckerman (FOCS 2012) (which gives a seed length of s1/2+o(1) for arbitrary branching programs of size s). Our techniques also give seed length n1/2+o(1) for general oblivious, read-once branching programs of width 2no(1), which is incomparable to the results of Impagliazzo et al.

Our pseudorandom generator is similar to the one used by Gopalan et al. (FOCS 2012) for read-once CNFs, but the analysis is quite different; ours is based on Fourier analysis of branching programs. In particular, we show that an oblivious, read-once, regular branching program of width w has Fourier mass at most (2w2)k at level k, independent of the length of the program.

Joint work with Omer Reingold and Salil Vadhan. See the ECCC report.