Poly-logarithmic independence fools AC0 circuits

by Mark Braverman

Oded's comments

Just see the original abstract.

The original abstract

We prove that poly-sized AC0 circuits cannot distinguish a poly-logarithmically 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.


Back to list of Oded's choices.