ECCC-Report TR09-141https://eccc.weizmann.ac.il/report/2009/141Comments and Revisions published for TR09-141en-usSat, 19 Dec 2009 21:08:57 +0200
Paper TR09-141
| Improved Pseudorandom Generators for Depth 2 Circuits |
Luca Trevisan,
Anindya De,
Omid Etesami,
Madhur Tulsiani
https://eccc.weizmann.ac.il/report/2009/141We 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.Sat, 19 Dec 2009 21:08:57 +0200https://eccc.weizmann.ac.il/report/2009/141