Poly-logarithmic independence fools AC0 circuits

Mark Braverman

doi:10.1109/CCC.2009.35

Poly-logarithmic independence fools AC⁰ circuits

Mark Braverman

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

25 Scopus citations

Abstract

We prove that poly-sized AC⁰ 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²n)- independent distributions fool poly-size DNF formulas. Razborov [Raz08] has later given a much simpler proof for Bazzi's theorem.

Original language	English (US)
Title of host publication	Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009
Pages	3-8
Number of pages	6
DOIs	https://doi.org/10.1109/CCC.2009.35
State	Published - 2009
Externally published	Yes
Event	2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009 - Paris, France Duration: Jul 15 2009 → Jul 18 2009

Publication series

Name	Proceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)	1093-0159

Other

Other	2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009
Country/Territory	France
City	Paris
Period	7/15/09 → 7/18/09

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Computational Mathematics

Access to Document

10.1109/CCC.2009.35

Cite this

@inproceedings{c23036535ba24bc98a3a4c6f77995869,

title = "Poly-logarithmic independence fools AC0 circuits",

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 Bazzi's theorem.",

author = "Mark Braverman",

year = "2009",

doi = "10.1109/CCC.2009.35",

language = "English (US)",

isbn = "9780769537177",

series = "Proceedings of the Annual IEEE Conference on Computational Complexity",

pages = "3--8",

booktitle = "Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009",

note = "2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009 ; Conference date: 15-07-2009 Through 18-07-2009",

}

Braverman, M 2009, Poly-logarithmic independence fools AC⁰ circuits. in Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009., 5231177, Proceedings of the Annual IEEE Conference on Computational Complexity, pp. 3-8, 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 7/15/09. https://doi.org/10.1109/CCC.2009.35

TY - GEN

T1 - Poly-logarithmic independence fools AC0 circuits

AU - Braverman, Mark

PY - 2009

Y1 - 2009

N2 - 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 Bazzi's theorem.

AB - 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 Bazzi's theorem.

UR - http://www.scopus.com/inward/record.url?scp=70350367955&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350367955&partnerID=8YFLogxK

U2 - 10.1109/CCC.2009.35

DO - 10.1109/CCC.2009.35

M3 - Conference contribution

AN - SCOPUS:70350367955

SN - 9780769537177

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 3

EP - 8

BT - Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009

T2 - 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009

Y2 - 15 July 2009 through 18 July 2009

ER -