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

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

Justin Thaler, Mark Bun

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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Agnostically Learning Halfspaces
• Perceptrons, PP, and the polynomial hierarchy
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Uniform Lower Bound on Weights of Perceptrons
• Title not available (Why is that?)
• 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
• Separations in Query Complexity Based on Pointer 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
• Title not available (Why is that?)
• Dual lower bounds for approximate degree and Markov-Bernstein inequalities
• 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
• Title not available (Why is that?)
• The Intersection of Two Halfspaces Has High Threshold Degree
• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
• 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
• Title not available (Why is that?)
• Dual polynomials for collision and element distinctness
• Breaking the minsky-papert barrier for constant-depth circuits
• Improved Bounds on the Sign-Rank of AC^0
• The log-approximate-rank conjecture is false
• Adaptivity vs. Postselection, and Hardness Amplification for Polynomial Approximation

Cited In (5)

• A Short List of Equalities Induces Large Sign-Rank
• Algorithmic Polynomials
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
• Title not available (Why is that?)
• Approximate Degree in Classical and Quantum Computing

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)