Polylogarithmic independence fools AC0 circuits

Mark Braverman

doi:10.1145/1754399.1754401

Polylogarithmic independence fools AC⁰ circuits

Mark Braverman

Research output: Contribution to journal › Article › peer-review

77 Scopus citations

Abstract

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

Original language	English (US)
Article number	28
Journal	Journal of the ACM
Volume	57
Issue number	5
DOIs	https://doi.org/10.1145/1754399.1754401
State	Published - Jun 2010
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence

Keywords

Circuit complexity
Lower bounds
Polynomial approximations
Pseudorandomness

Access to Document

10.1145/1754399.1754401

Cite this

@article{08235ba7e19c41e38b86e5e37ab02d67,

title = "Polylogarithmic independence fools AC0 circuits",

abstract = "We prove that poly-sized AC0 circuits cannot distinguish a polylogarithmically 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(log2n)-independent distributions fool poly-size DNF formulas. [Razborov 2008] has later given a much simpler proof for Bazzi's theorem.",

keywords = "Circuit complexity, Lower bounds, Polynomial approximations, Pseudorandomness",

author = "Mark Braverman",

year = "2010",

month = jun,

doi = "10.1145/1754399.1754401",

language = "English (US)",

volume = "57",

journal = "Journal of the ACM",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "5",

}

TY - JOUR

T1 - Polylogarithmic independence fools AC0 circuits

AU - Braverman, Mark

PY - 2010/6

Y1 - 2010/6

N2 - We prove that poly-sized AC0 circuits cannot distinguish a polylogarithmically 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(log2n)-independent distributions fool poly-size DNF formulas. [Razborov 2008] has later given a much simpler proof for Bazzi's theorem.

AB - We prove that poly-sized AC0 circuits cannot distinguish a polylogarithmically 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(log2n)-independent distributions fool poly-size DNF formulas. [Razborov 2008] has later given a much simpler proof for Bazzi's theorem.

KW - Circuit complexity

KW - Lower bounds

KW - Polynomial approximations

KW - Pseudorandomness

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

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

U2 - 10.1145/1754399.1754401

DO - 10.1145/1754399.1754401

M3 - Article

AN - SCOPUS:77954011327

SN - 0004-5411

VL - 57

JO - Journal of the ACM

JF - Journal of the ACM

IS - 5

M1 - 28

ER -