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 $\tilde{O}({\log }^{3}n).$ The previously best known seed length for this model is $n^{1/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 \textit{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:\{0,1{\}}^n\to \{0,1\}$ computed by such a branching program, and $k\in [n],$ $$\sum _{s\subseteq [n]:|s|=k}\left|\hat{f}[s]\right|\le n^2\cdot (O(\log n){)}^k,$$ where $\hat{f}[s]=\mathbb{E}\left[f[U]\cdot (-1{)}^{s\cdot U}\right]$ is the standard Fourier transform over ${\mathbb{Z}}_2^n$. The base $O(\log n)$ of the Fourier growth is tight up to a factor of $\log \log n$.

arXiv admin note: text overlap with arXiv:1306.3004

Cited by in corpus (1)

• Fourier bounds and pseudorandom generators for product tests