Theory of Computing
-------------------
Title : Pseudorandomness for Width-2 Branching Programs
Authors : Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff
Volume : 9
Number : 7
Pages : 283-293
URL : https://theoryofcomputing.org/articles/v009a007
Abstract
--------
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)$.