Pseudorandomness for Regular Branching Programs via Fourier Analysis

Omer Reingold Thomas Steinke Salil Vadhan

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(log2 n), where n is the length of the branching program. The previous best seed length known for this model was n½+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½+o(1) for arbitrary branching programs of size s). Our techniques also give seed length n½+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 (2w)2k at level k, independent of the length of the program.

Published: RANDOM 2013
Full Version: arXiv
Bibtex:  
@inproceedings{ReingoldSteinkeVadhan2013,
   author = {Omer Reingold and Thomas Steinke and Salil Vadhan},
   title = {Pseudorandomness for Regular Branching Programs via Fourier Analysis},
   booktitle = {APPROX-RANDOM},
   year = {2013},
   pages = {655--670},
   publisher = {Springer},
   series = {Lecture Notes in Computer Science},
   editor = {Prasad Raghavendra and Sofya Raskhodnikova and Klaus Jansen and Jos\'e Rolim}

Last updated on 12 June 2013 by Thomas Steinke.