Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-070 | 1st September 2009 23:39

Pseudorandomness for Width 2 Branching Programs


Authors: Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff
Publication: 3rd September 2009 08:35
Downloads: 3571


Bogdanov and Viola (FOCS 2007) constructed a pseudorandom
generator that fools degree $k$ polynomials over $\F_2$ for an arbitrary
constant $k$. We show that such generators can also be used to fool branching programs of width 2 and polynomial length that read $k$ bits of inputs at a
time. This model generalizes polynomials of degree $k$ over $\F_2$
and includes some other interesting classes of functions, for
instance $k$-DNF.

The construction of Bogdanov and Viola consists of
summing $k$ independent copies of a generator that $\epsilon$-fools
linear functions (an $\epsilon$-biased set). 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)$.

ISSN 1433-8092 | Imprint