Polylogarithmic independence fools AC0 circuits

Research output: Contribution to journalArticle

55 Scopus citations

Abstract

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

Original languageEnglish (US)
Article number28
JournalJournal of the ACM
Volume57
Issue number5
DOIs
StatePublished - Jun 1 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Circuit complexity
  • Lower bounds
  • Polynomial approximations
  • Pseudorandomness

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

  • Cite this