Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NISAN-LINIAL CONJECTURE:
Reports tagged with Nisan-Linial conjecture:
TR09-011 | 31st January 2009
Mark Braverman

Poly-logarithmic independence fools AC0 circuits

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 [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 ... more >>>




ISSN 1433-8092 | Imprint