Polylogarithmic Independence Fools AC(0) Circuits
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.
theory circuit complexity pseudorandomness polynomial approximations lower bounds