TR09-070 Authors: Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff

Publication: 3rd September 2009 08:35

Downloads: 2893

Keywords:

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)$.