@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\&nbsp;in the\&nbsp;Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM{\textquoteright}14).\&nbsp;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\&nbsp;\({\~O}(\log^3\&nbsp;n)\).The previously best known seed length for this model is\&nbsp;\(n^{1/2+o(1)}\)\&nbsp;due to Impagliazzo, Meka, and Zuckerman (FOCS {\textquoteright}12). Our work generalizes a recent result of Reingold, Steinke, and Vadhan (RANDOM {\textquoteright}13) for\&nbsp;permutation\&nbsp;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\&nbsp;\(f\&nbsp;:\&nbsp;\{0,\&nbsp;1\}^n\&nbsp;{\textrightarrow} \{0,\&nbsp;1\}\)\&nbsp;computed by such a branching program, and\&nbsp;\(k\&nbsp;∈\&nbsp;[n]\),



	\&nbsp;\(\displaystyle\sum_{s⊆[n]:|s|=k} \big| \hat{f}[s] \big | <=n^2\&nbsp;{\textperiodcentered}(O(\log n))^k\),



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

},
	url = {https://theoryofcomputing.org/articles/v013a012/},
	author = {Thomas Steinke and Salil Vadhan and Andrew Wan}
}
