Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs

Thomas Steinke Salil Vadhan Andrew Wan

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 previously best known seed length for this model is n1/2+o(1) due to Impagliazzo, Meka, and Zuckerman (FOCS '12). Our work 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 g : {0,1}n → {0,1} computed by such a branching program, and k ∈ [n],

s ⊂ [n] : |s|=k | ĝ[s] | ≤ n2 (O(log n))k,

where ĝ[s] = Ex[g[U] (-1)s . U] is the standard Fourier transform over Z2n. The base O(log n) of the Fourier growth is tight up to a factor of log log n.

Full Version: ECCC [PDF]
Proceedings: RANDOM 2014
Bibtex:  
@inproceedings{SteinkeVadhanWan2014,
   author = {Thomas Steinke and Salil Vadhan and Andrew Wan},
   title = {Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs},
   booktitle ={ Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
   pages = {885--899},
   series = {Leibniz International Proceedings in Informatics (LIPIcs)},
   ISBN ={978-3-939897-74-3},
   ISSN ={1868-8969},
   year ={2014},
   volume ={28},
   editor ={Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
   publisher ={Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
   address ={Dagstuhl, Germany},
   URL ={http://drops.dagstuhl.de/opus/volltexte/2014/4745},
   URN ={urn:nbn:de:0030-drops-47456},
   doi ={http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.885},
   annote ={Keywords: Pseudorandomness, Branching Programs, Discrete Fourier Analysis}

Last updated on 7 Oct 2014 by Thomas Steinke.