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 n12+o(1) , which follows as a specialcase of a generator due to Impagliazzo, Meka, and Zuckerman (FOCS 2012) (which gives a seed length ofs12+o(1) for arbitrary branching programs of size s). Our techniques also give seed length n12+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.