Polylogarithmic independence fools AC 0 circuits
Mark Braverman · Journal of the ACM · 2008
We prove that poly-sized AC 0 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 (log 2 n )-independent distributions fool poly-size DNF formulas. [Razborov 2008] has later given a much simpler proof for Bazzi's theorem.