Improved Pseudorandom Generators for Depth 2 Circuits

摘要

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 2 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 l/m~(O(log mn))-biased distribution 1/poly(nm)-ioos DNFs with m terms and n variables. For inverse polynomial distinguishing probability this is nearly tight because we show that for every m, S there is a 1/m~(Ω(log 1/δ))-biased distribution X and a DNF φ with m terms such that φ is not δ-fooled by X. For the case of read-once DNFs, we show that seed length O(logmn ? log 1/δ) suffices, which is an improvement for large δ. It also follows from our proof that a l/m~(O(log 1/δ))-biased distribution δ-fools all read-once DNF with m terms. We show that this result too is nearly tight, by constructing a l/m~(Ω(log 1/δ))-biased distribution that does not δ-fool a certain m-term read-once DNF. DNF, pseudorandom generators, small bias spaces