Poly-logarithmic Independence Fools AC⁰ Circuits

We prove that poly-sized AC 0 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(log 2 n)-independent distributions fool poly-size DNF formulas. Razborov Raz08 has later given a much simpler proof for Bazzipsilas theorem.