Polylogarithmic independence fools AC0 circuits

Research output: Contribution to journalArticlepeer-review

71 Scopus citations


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
Issue number5
StatePublished - Jun 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


  • Circuit complexity
  • Lower bounds
  • Polynomial approximations
  • Pseudorandomness


Dive into the research topics of 'Polylogarithmic independence fools AC0 circuits'. Together they form a unique fingerprint.

Cite this