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

DOI10.1137/17M1161737zbMATH Open1471.68092arXiv1703.05784OpenAlexW2981639918MaRDI QIDQ5117375FDOQ5117375

Authors: Mark Bun, Justin Thaler 

Publication date: 25 August 2020

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

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$.

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

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

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)

Cites Work

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

Cited In (14)

• 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\)
• 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
• Title not available (Why is that?)
• Near-optimal lower bounds on the threshold degree and sign-rank of \(\mathrm{AC}^0\)
• Approximate Degree in Classical and Quantum Computing
• Lower bounds for the approximate degree of block-composed functions

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)