Pseudorandomness for Regular Branching Programs via Fourier Analysis

Abstract

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(log^2 n)\), where n is the length of the branching program. The previous best seed length known for this model was \(n^{ 1/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 \(s^{ 1/2 + o(1)}\) for arbitrary branching programs of size s). Our techniques also give seed length \(n^{ 1/2 + o(1)}\) for general oblivious, read-once branching programs of width \(2^{n^{o(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 \((2w^ 2) ^k\) at level k, independent of the length of the program.