Pseudorandomness and Fourier growth bounds for width 3 branching programs

Citation:

Steinke, Thomas, Salil Vadhan, and Andrew Wan. “Pseudorandomness and Fourier growth bounds for width 3 branching programs.” Theory of Computing – Special Issue on APPROX-RANDOM 2014 13, no. 12 (2017): 1-50.
 TOC 2017.pdf 446 KB APPROX-RANDOM 2014.pdf 559 KB ArXiv 2014.pdf 430 KB

Abstract:

Version History: a conference version of this paper appeared in the Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM'14). Full version posted as ECCC TR14-076 and arXiv:1405.7028 [cs.CC].

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 $$Õ(\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 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 → \{0, 1\}$$ computed by such a branching program, and $$k ∈ [n]$$,

$$\displaystyle\sum_{s⊆[n]:|s|=k} \big| \hat{f}[s] \big | ≤n^2 ·(O(\log n))^k$$,

where $$\hat{f}[s] = \mathbb{E}_U [f[U] \cdot (-1)^{s \cdot U}]$$ is the standard Fourier transform over $$\mathbb{Z}^n_2$$. The base $$O(\log n)$$ of the Fourier growth is tight up to a factor of $$\log \log n$$.

Publisher's Version

Last updated on 06/30/2020