Pseudorandomness for Regular Branching Programs via Fourier Analysis
Preprint
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)^{2k}$ at level $k$, independent of the length of the program.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Pseudorandomness for Read-Once Formulas2011
- Balls and Bins: Smaller Hash Families and Faster Evaluation2011
- Undirected connectivity in log-spaceJournal of the ACM, 2008
- Stable distributions, pseudorandom generators, embeddings, and data stream computationJournal of the ACM, 2006
- Using Nondeterminism to Amplify HardnessSIAM Journal on Computing, 2006
- Discrepancy sets and pseudorandom generators for combinatorial rectangles2002
- Improved Pseudorandom Generators for Combinatorial RectanglesCombinatorica, 2002
- Efficient construction of a small hitting set for combinatorial rectangles in high dimensionCombinatorica, 1997
- Chernoff–Hoeffding Bounds for Applications with Limited IndependenceSIAM Journal on Discrete Mathematics, 1995
- Small-Bias Probability Spaces: Efficient Constructions and ApplicationsSIAM Journal on Computing, 1993