Volume 9 (2013) Article 7 pp. 283-293

Pseudorandomness for Width-2 Branching Programs

by Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff

Received: September 4, 2009
Revised: October 10, 2012
Published: February 27, 2013

$\newcommand\F{{\mathbb{F}}}$

We show that pseudorandom generators that fool degree-$k$ polynomials over $\F_2$ also fool branching programs of width-$2$ and polynomial length that read $k$ bits of input at a time. This model generalizes polynomials of degree $k$ over $\F_2$ and includes some other interesting classes of functions, for instance, $k$-DNFs.

The proof essentially follows by a new decomposition theorem for width-$2$ branching programs. The theorem states that if $f$ can be computed by a width-$2$ branching program that reads $k$ bits of input at a time, then $f$ can be (roughly) written as a sum $f = \sum_i \alpha_i f_i$ where each $f_i$ is a degree-$k$ polynomial and $\sum_i |\alpha_i|$ is small.

Bogdanov and Viola (FOCS 2007) constructed a pseudorandom generator that fools degree-$k$ polynomials over $\F_2$ for arbitrary $k$. Their construction consists of summing $k$ independent copies of a generator that $\epsilon$-fools linear functions. Our second result investigates the limits of such constructions: We show that, in general, such a construction is not pseudorandom against bounded fan-in circuits of depth $O((\log(k \log 1/\epsilon))^2)$.

DOI: 10.4086/toc.2013.v009a007

© 2013 Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff
Licensed under a Creative Commons Attribution License (CC-BY)