July 1, 2009

Poly-logarithmic Independence Fools AC⁰ Circuits

Key Points

Key points are not available for this paper at this time.

Abstract

We prove that poly-sized AC 0 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 later given a much simpler proof for Bazzipsilas theorem.

Ask AI

Helpful

Bookmark

View Full Paper

Cite This Study

Mark Braverman (Wed,) studied this question.

synapsesocial.com/papers/6a20ed4e5496711a5f2ab22c https://doi.org/https://doi.org/10.1109/ccc.2009.35

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

1A Simple Proof of Bazzi’s Theorem2009 · 48 citations
2Polylogarithmic Independence Can Fool DNF Formulas2009 · 74 citations
3NP is as easy as detecting unique solutions1985 · 128 citations
4Algebraic methods in the theory of lower bounds for Boolean circuit complexity1987 · 760 citations
5Approximate Inclusion-Exclusion1990 · 98 citations

Ask AI

Helpful

Bookmark

View Full Paper