Improved pseudorandom generators for depth 2 circuits

Anindya De*, Omid Etesami, Luca Trevisan, Madhur Tulsiani

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

33 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings
Pages504-517
Number of pages14
DOIs
StatePublished - Nov 15 2010
Event13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010 - Barcelona, Spain
Duration: Sep 1 2010Sep 3 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6302 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010
CountrySpain
CityBarcelona
Period9/1/109/3/10

Keywords

  • DNF
  • pseudorandom generators
  • small bias spaces

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Improved pseudorandom generators for depth 2 circuits'. Together they form a unique fingerprint.

Cite this