TR09-141 Authors: Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani

Publication: 19th December 2009 21:08

Downloads: 2440

Keywords:

We prove the existence of a $poly(n,m)$-time computable

pseudorandom generator which ``$1/poly(n,m)$-fools'' DNFs with $n$ variables

and $m$ terms, and has seed length $O(\log^2 nm \cdot \log\log nm)$.

Previously, the best pseudorandom generator for depth-2 circuits had seed

length $O(\log^3 nm)$, and was due to Bazzi (FOCS 2007).

It follows from our proof

that a $1/m^{\tilde O(\log mn)}$-biased distribution $1/poly(nm)$-fools DNFs

with $m$ terms and $n$ variables. For inverse polynomial distinguishing probability

this is nearly tight because we show that for every $m,\delta$

there is a $1/m^{\Omega(\log 1/\delta)}$-biased

distribution $X$ and a DNF $\phi$ with $m$ terms such that $\phi$ is

not $\delta$-fooled by $X$.

For the case of {\em read-once} DNFs, we show that seed length

$O(\log mn \cdot \log 1/\delta)$ suffices, which is an improvement for large $\delta$.

It also follows from our proof that a $1/m^{O(\log 1/\delta)}$-biased distribution

$\delta$-fools all read-once DNF with $m$ terms. We show that this result too is nearly tight,

by constructing a $1/m^{\tilde \Omega(\log 1/\delta)}$-biased distribution

that does not $\delta$-fool a certain $m$-term read-once DNF.