pdf icon
Volume 13 (2017) Article 12 pp. 1-50
APPROX-RANDOM 2014 Special Issue
Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs
Received: February 23, 2015
Revised: December 20, 2016
Published: October 31, 2017
Download article from ToC site:
[PDF (446K)]    [PS (6605K)]    [PS.GZ (892K)]
[Source ZIP]
Keywords: pseudorandom generators, branching programs, Fourier analysis
ACM Classification: F.1
AMS Classification: 68Q17, 52C07, 11H06, 11H31, 05B40

Abstract: [Plain Text Version]

$ \newcommand{\ex}[2]{\underset{#1}{\mathbb{E}}\left[ #2 \right]} \newcommand{\tO}{\widetilde{O}} $

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 $\tO( \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} \left| \widehat{f}[s] \right| \leq n^2 \cdot (O(\log n))^k,$$ where $\widehat{f}[s] = \ex{U}{f[U] \cdot (-1)^{s \cdot U}}$ 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$.

A conference version of this paper appeared in the , Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM'14).