Theory of Computing
-------------------
Title : Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs
Authors : Thomas Steinke, Salil Vadhan, and Andrew Wan
Volume : 13
Number : 12
Pages : 1-50
URL : http://www.theoryofcomputing.org/articles/v013a012
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 $O~(\log^3 n).$ The best
previously known seed length for this model is $n^{1/2+o(1)}$ due
to Impagliazzo, Meka, and Zuckerman (FOCS'12). Our result 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\rightarrow \{0,1\}$ computed by such a
branching program, and $k\in [n],$
$$\sum_{s\subseteq [n]: |s|=k}|\hat{f}[s]|\leq n^2 (O(\log n))^k,$$
where $\hat{f}[s] = E_{U}(f[U] (-1)^{sU})$ is the standard
Fourier transform over $Z_2^n$. The base $O(\log n)$ of the
Fourier growth is tight up to a factor of $\log\log n$.
A conference version of this paper appeared in the
Proceedings of the 18th International Workshop on
Randomization and Computation (RANDOMâ€™14).