Poly-logarithmic independence fools AC0 circuits

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

23 Scopus citations

Abstract

We prove that poly-sized AC0 circuits cannot distinguish a poly-logarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [LN90]. The only prior progress on the problem was by Bazzi [Baz07], who showed that O(log2n)- independent distributions fool poly-size DNF formulas. Razborov [Raz08] has later given a much simpler proof for Bazzi's theorem.

Original languageEnglish (US)
Title of host publicationProceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009
Pages3-8
Number of pages6
DOIs
StatePublished - Nov 9 2009
Externally publishedYes
Event2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009 - Paris, France
Duration: Jul 15 2009Jul 18 2009

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

Other2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009
CountryFrance
CityParis
Period7/15/097/18/09

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Poly-logarithmic independence fools AC<sup>0</sup> circuits'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M. (2009). Poly-logarithmic independence fools AC0 circuits. In Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009 (pp. 3-8). [5231177] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2009.35