@article {634027,
title = {Pseudorandomness and Fourier growth bounds for width 3 branching programs},
journal = {Theory of Computing {\textendash} Special Issue on APPROX-RANDOM 2014},
volume = {13},
number = {12},
year = {2017},
pages = {1-50},
publisher = {Leibniz International Proceedings in Informatics (LIPIcs)},
abstract = {
Version History: a conference version of this paper appeared\ in the\ Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM{\textquoteright}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\ \({\~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 {\textquoteright}12). Our work generalizes a recent result of Reingold, Steinke, and Vadhan (RANDOM {\textquoteright}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\ {\textrightarrow} \{0,\ 1\}\)\ computed by such a branching program, and\ \(k\ ā\ [n]\),
\ \(\displaystyle\sum_{sā[n]:|s|=k} \big| \hat{f}[s] \big | <=n^2\ {\textperiodcentered}(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\).
},
url = {https://theoryofcomputing.org/articles/v013a012/},
author = {Thomas Steinke and Salil Vadhan and Andrew Wan}
}