aqora

Approximate Degree and the Complexity of Depth Three Circuits.

Mark Bun, Justin Thaler

Electronic colloquium on computational complexityJan 1, 20166 citations

Approximate counting with uniform constant depth circuits

Miklós Ajtai

DIMACS series in discrete mathematics and theoretical computer scienceOct 25, 199349 citations

Circuit Complexity and Approximate Operations

Kazuyuki Amano, Akira Maruoka

Proceedings of the IEICE General ConferenceMar 6, 19970 citations

The Power of Asymmetry in Constant-Depth Circuits

Alexander A. Sherstov

The threshold degree of a Boolean function f is the minimum degree of a real polynomial p that represents f in sign: f(x) = sgn p(x). Introduced in the seminal work of Minsky and Papert (1969), this notion is central to some of the strongest algorithmic and complexity-theoretic results for constant-depth circuits. One problem that has remained open for several decades, with applications to computational learning and communication complexity, is to determine the maximum threshold degree of a polynomial-size constant-depth circuit in n variables. The best lower bound prior to our work was Ω(n(d-1)/(2d-1)) for circuits of depth d. We obtain a polynomial improvement for every depth d, with a lower bound of Ω(n3/7) for depth 3 and Ω(√n) for depth d ≥4. The proof contributes a novel approximation-theoretic technique of independent interest, which exploits asymmetry in circuits to prove their hardness for polynomials.The threshold degree of a Boolean function f is the minimum degree of a real polynomial p that represents f in sign: f(x) = sgn p(x). Introduced in the seminal work of Minsky and Papert (1969), this notion is central to some of the strongest algorithmic and complexity-theoretic results for constant-depth circuits. One problem that has remained open for several decades, with applications to computational learning and communication complexity, is to determine the maximum threshold degree of a polynomial-size constant-depth circuit in n variables. The best lower bound prior to our work was Ω(n(d-1)/(2d-1)) for circuits of depth d. We obtain a polynomial improvement for every depth d, with a lower bound of Ω(n3/7) for depth 3 and Ω(√n) for depth d ≥4. The proof contributes a novel approximation-theoretic technique of independent interest, which exploits asymmetry in circuits to prove their hardness for polynomials.

Annual Symposium on Foundations of Computer ScienceOct 1, 201514 citations

Degradation and Amplification of Computational Hardness

Shai Halevi, Tal Rabin

Springer eBooksFeb 25, 200815 citations

The approximate degree of DNF and CNF formulas

Alexander A. Sherstov

The approximate degree of a Boolean function f∶{0,1}n→{0,1} is the minimum degree of a real polynomial p that approximates f pointwise: |f(x)−p(x)|≤1/3 for all x∈{0,1}n. For any δ>0, we construct DNF and CNF formulas of polynomial size with approximate degree Ω(n1−δ), essentially matching the trivial upper bound of n. This fully resolves the approximate degree of constant-depth circuits (AC0), a question that has seen extensive research over the past 10 years. Prior to our work, an Ω(n1−δ) lower bound was known only for AC0 circuits of depth that grows with 1/δ (Bun and Thaler, FOCS 2017). Furthermore, the DNF and CNF formulas that we construct are the simplest possible in that they have constant width.The approximate degree of a Boolean function f∶{0,1}n→{0,1} is the minimum degree of a real polynomial p that approximates f pointwise: |f(x)−p(x)|≤1/3 for all x∈{0,1}n. For any δ>0, we construct DNF and CNF formulas of polynomial size with approximate degree Ω(n1−δ), essentially matching the trivial upper bound of n. This fully resolves the approximate degree of constant-depth circuits (AC0), a question that has seen extensive research over the past 10 years. Prior to our work, an Ω(n1−δ) lower bound was known only for AC0 circuits of depth that grows with 1/δ (Bun and Thaler, FOCS 2017). Furthermore, the DNF and CNF formulas that we construct are the simplest possible in that they have constant width.

ACM Symposium on Theory of Computing (STOC)Jun 9, 20222 citations

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits

Related papers

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits

Related papers