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.