Title :
Poly-logarithmic Independence Fools AC^0 Circuits
Author_Institution :
Microsoft Res. New England, Cambridge, MA, USA
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 [LN90]. The only prior progress on the problem was by Bazzi [Baz07], who showed that O(log2n)-independent distributions fool poly-size DNF formulas. Razborov [Raz08] has later given a much simpler proof for Bazzipsilas theorem.
Keywords :
circuit complexity; statistical distributions; Bazzi theorem proof; poly-logarithmically independent distribution; poly-size DNF formula; poly-sized AC0 circuit complexity; Boolean functions; Circuits; Computational complexity; Distributed computing; Drives; Linear code; Polynomials; USA Councils; circuit complexity; polynomial approximation; pseudorandomness;
Conference_Titel :
Computational Complexity, 2009. CCC '09. 24th Annual IEEE Conference on
Conference_Location :
Paris
Print_ISBN :
978-0-7695-3717-7
DOI :
10.1109/CCC.2009.35
