A nearly optimal lower bound on the approximate degree of AC^0

DOI10.1137/17M1161737MaRDI QIDQ5117375zbMATH OpenOpenAlexFDO

Authors Mark Bun, Justin Thaler

Publication date 25 August 2020

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.05784

zbMATH Keywords

Boolean functionsecret-sharing schemeapproximate degreeconstant-depth circuitcertificate complexityquantum communication complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Authentication, digital signatures and secret sharing (94A62) Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11)

Abstract: The approximate degree of a Boolean function $fcolon{-1,1}^{n}ightarrow-1,1$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function $f$ with approximate degree $d$ into a function $F$ on $O(ncdotoperatornamepolylog(n))$ variables with approximate degree at least $D=Omega(n^{1/3}cdot{d}^{2/3})$. In particular, if $d=n^{1-Omega(1)}$, then $D$ is polynomially larger than $d$. Moreover, if $f$ is computed by a polynomial-size Boolean circuit of constant depth, then so is $F$. By recursively applying our transformation, for any constant $delta>0$ we exhibit an AC${}^0$ function of approximate degree $Omega(n^{1-delta})$. This improves over the best previous lower bound of $Omega(n^{2/3})$ due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of $n$ that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: * For any constant $delta>0$, an $Omega(n^{1-delta})$ lower bound on the quantum communication complexity of a function in AC${}^0$. * A Boolean function $f$ with approximate degree at least $C(f{)}^{2-o(1)}$, where $C(f)$ is the certificate complexity of $f$. This separation is optimal up to the $o(1)$ term in the exponent. * Improved secret sharing schemes with reconstruction procedures in AC${}^0$.

Recommendations

• Hardness amplification and the approximate degree of constant-depth circuits
• Near-optimal lower bounds on the threshold degree and sign-rank of \(\mathrm{AC}^0\)
• scientific article; zbMATH DE number 6861917
• Approximating the AND-OR tree
• Algorithmic Polynomials

Cites work

• scientific article; zbMATH DE number 5899233 (Why is no real title available?)
• scientific article; zbMATH DE number 5605137 (Why is no real title available?)
• scientific article; zbMATH DE number 5568623 (Why is no real title available?)
• scientific article; zbMATH DE number 2038718 (Why is no real title available?)
• scientific article; zbMATH DE number 7204275 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• A Uniform Lower Bound on Weights of Perceptrons
• A separation of NP and conp in multiparty communication complexity
• Adaptivity vs. postselection, and hardness amplification for polynomial approximation
• Agnostically Learning Halfspaces
• Algorithmic polynomials
• Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
• Approximate inclusion-exclusion for arbitrary symmetric functions
• Approximating the AND-OR tree
• Bounded indistinguishability and the complexity of recovering secrets
• Breaking the Minsky-Papert barrier for constant-depth circuits
• Communication lower bounds using directional derivatives
• Deterministic communication vs. partition number
• Disjointness is hard in the multiparty number-on-the-forehead model
• Dual polynomials for collision and element distinctness
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Formula lower bounds via the quantum method
• Hardness amplification and the approximate degree of constant-depth circuits
• Impossibility of succinct quantum proofs for collision-freeness
• Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
• Improved separations between nondeterministic and randomized multiparty communication
• Inclusion-exclusion: exact and approximate
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Lower bounds for the approximate degree of block-composed functions
• Making polynomials robust to noise
• Multiparty communication complexity and threshold circuit size of AC^0
• New degree bounds for polynomial threshold functions
• On the degree of Boolean functions as real polynomials
• One-way functions and the nonisomorphism of NP-complete sets
• Perceptrons, PP, and the polynomial hierarchy
• Quantum lower bounds by polynomials
• Quantum lower bounds for the collision and the element distinctness problems
• Query complexity, or why is it difficult to separate NP^ A coNP^ A from P^ A by random oracles A?
• Separating AC\(^0\) from depth-2 majority circuits
• Separations in query complexity using cheat sheets
• Simplified lower bounds on the multiparty communication complexity of disjointness
• The Sign-Rank of AC^0
• The intersection of two halfspaces has high threshold degree
• The log-approximate-rank conjecture is false
• The multiparty communication complexity of set disjointness
• The pattern matrix method
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• The quantum query complexity of \(\mathrm{AC}^0\)
• The quantum query complexity of read-many formulas
• Toward attribute efficient learning of decision lists and parities

Cited in

(16)

• Lower bounds for the approximate degree of block-composed functions
• On polynomial approximations to \(\mathrm{AC}^0\)
• Algorithmic Polynomials
• Approximating the AND-OR tree
• Lower bounding the AND-OR tree via symmetrization
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
• A short list of equalities induces large sign-rank
• The large-error approximate degree of \(\mathrm{AC}^0\)
• Separations between combinatorial measures for transitive functions
• The large-error approximate degree of \(\mathrm{AC}^0\)
• Optimal bounds on the approximation of Boolean functions with consequences on the concept of hardness
• Hardness amplification and the approximate degree of constant-depth circuits
• scientific article; zbMATH DE number 522838 (Why is no real title available?)
• Near-optimal lower bounds on the threshold degree and sign-rank of \(\mathrm{AC}^0\)
• Approximate Degree in Classical and Quantum Computing
• The approximate degree of DNF and CNF formulas

This page was built for publication: A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5117375)