TY - GEN

T1 - Improved pseudorandom generators for depth 2 circuits

AU - De, Anindya

AU - Etesami, Omid

AU - Trevisan, Luca

AU - Tulsiani, Madhur

PY - 2010/11/15

Y1 - 2010/11/15

N2 - 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(log2 nm·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Õ(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,δ there is a 1/mΩ(log1/δ)-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(log mn·log1/δ) suffices, which is an improvement for large δ. It also follows from our proof that a 1/m O(log1/δ)-biased distribution δ-fools all read-once DNF with m terms. We show that this result too is nearly tight, by constructing a 1/mΩ(log 1/δ)-biased distribution that does not δ-fool a certain m-term read-once DNF.

AB - 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(log2 nm·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Õ(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,δ there is a 1/mΩ(log1/δ)-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(log mn·log1/δ) suffices, which is an improvement for large δ. It also follows from our proof that a 1/m O(log1/δ)-biased distribution δ-fools all read-once DNF with m terms. We show that this result too is nearly tight, by constructing a 1/mΩ(log 1/δ)-biased distribution that does not δ-fool a certain m-term read-once DNF.

KW - DNF

KW - pseudorandom generators

KW - small bias spaces

UR - http://www.scopus.com/inward/record.url?scp=78149304713&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78149304713&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-15369-3_38

DO - 10.1007/978-3-642-15369-3_38

M3 - Conference contribution

AN - SCOPUS:78149304713

SN - 3642153682

SN - 9783642153686

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 504

EP - 517

BT - Approximation, Randomization, and Combinatorial Optimization

T2 - 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010

Y2 - 1 September 2010 through 3 September 2010

ER -