Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



TR09-141 | 19th December 2009 21:08

Improved Pseudorandom Generators for Depth 2 Circuits


Authors: Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani
Publication: 19th December 2009 21:08
Downloads: 1887


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.

ISSN 1433-8092 | Imprint