We prove the existence of a poly(nm) -time computablepseudorandom generator which ``1poly(nm) -fools'' DNFs with n variablesand m terms, and has seed length O(log2nmloglognm).Previously, the best pseudorandom generator for depth-2 circuits had seedlength O(log3nm), and was due to Bazzi (FOCS 2007).
It follows from our proofthat a 1mO(logmn) -biased distribution 1poly(nm) -fools DNFswith m terms and n variables. For inverse polynomial distinguishing probabilitythis is nearly tight because we show that for every m there is a 1m(log1) -biaseddistribution X and a DNF with m terms such that isnot -fooled by X.
For the case of {\em read-once} DNFs, we show that seed lengthO(logmnlog1) suffices, which is an improvement for large .
It also follows from our proof that a 1mO(log1) -biased distribution-fools all read-once DNF with m terms. We show that this result too is nearly tight,by constructing a 1m(log1) -biased distributionthat does not -fool a certain m-term read-once DNF