Pseudorandomness and fourier-growth bounds for width-3 branching programs

Abstract

We present an explicit pseudorandom generator for oblivious, read-once, width-3 branching programs, which can read their input bits in any order. The generator has seed length Õ(log3 n). The best previously known seed length for this model is n1/2+o(1) due to Impagliazzo, Meka, and Zuckerman (FOCS’12). Our result generalizes a recent result of Reingold, Steinke, and Vadhan (RANDOM’13) for permutation branching programs. The main technical novelty underlying our generator is a new bound on the Fourier growth of width-3, oblivious, read-once branching programs. Specifically, we show that for any f: f:{0.1}n →f:{0,1} computed by such a branching program, and k ∈ [n]; (Formula Presented.) where (Formula Presented.) is the standard Fourier transform over ℤn2. The base O(logn) of the Fourier growth is tight up to a factor of log logn.