Hardness amplification and the approximate degree of constant-depth circuits

DOI10.1007/978-3-662-47672-7_22MaRDI QIDQ3448791zbMATH OpenOpenAlexFDO

Authors Mark Bun, Justin Thaler

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32)

Abstract: We establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we show that if a Boolean circuit cannot be pointwise approximated by low-degree polynomials to within constant error in a certain one-sided sense, then an OR of disjoint copies of that circuit cannot be pointwise approximated even with very high error. As our main application, we show that for every sequence of degrees $d(n)$, there is an explicit depth-three circuit $F:{-1,1}^{n}o-1,1$ of polynomial-size such that any degree-$d$ polynomial cannot pointwise approximate $F$ to error better than $1-expleft(-ildeOmega(n{d}^{-3/2})ight)$. As a consequence of our main result, we obtain an $expleft(-ildeOmega(n^{2/5})ight)$ upper bound on the the discrepancy of a function in AC${}^0$, and an $expleft(ildeOmega(n^{2/5})ight)$ lower bound on the threshold weight of AC${}^0$, improving over the previous best results of $expleft(-Omega(n^{1/3})ight)$ and $expleft(Omega(n^{1/3})ight)$ respectively. Our techniques also yield a new lower bound of $Omegaleft(n^{1/2}/lo{g}^{(d-2)/2}(n)ight)$ on the approximate degree of the AND-OR tree of depth $d$, which is tight up to polylogarithmic factors for any constant $d$, as well as new bounds for read-once DNF formulas. In turn, these results imply new lower bounds on the communication and circuit complexity of these classes, and demonstrate strong limitations on existing PAC learning algorithms.

Recommendations

• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• Breaking the Minsky-Papert barrier for constant-depth circuits
• The power of asymmetry in constant-depth circuits
• Approximate degree and the complexity of depth three circuits
• Approximating the AND-OR tree

Cites work

• A separation of NP and conp in multiparty communication complexity
• Agnostically Learning Halfspaces
• Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
• Approximating the AND-OR tree
• Breaking the Minsky-Papert barrier for constant-depth circuits
• 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 2038718 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• New degree bounds for polynomial threshold functions
• On the computational power of Boolean decision lists
• On the computational power of depth-2 circuits with threshold and modulo gates
• On the degree of Boolean functions as real polynomials
• Perceptrons, PP, and the polynomial hierarchy
• Quantum lower bounds by polynomials
• Quantum lower bounds for the collision and the element distinctness problems
• Reflections for quantum query algorithms
• Reliable agnostic learning
• Separating AC\(^0\) from depth-2 majority circuits
• The Intersection of Two Halfspaces Has High Threshold Degree
• The multiparty communication complexity of set disjointness
• The pattern matrix method
• Toward attribute efficient learning of decision lists and parities

Cited in

(21)

• Learning \(\mathrm{AC}^0\) under \(k\)-dependent distributions
• ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
• Constant depth circuits, Fourier transform, and learnability
• An explicit VC-theorem for low-degree polynomials
• On uniform amplification of hardness in NP
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• The power of asymmetry in constant-depth circuits
• Lower bounds for the approximate degree of block-composed functions
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
• Approximate degree and the complexity of depth three circuits
• Approximate Degree in Classical and Quantum Computing
• Quantum lower bounds for approximate counting via Laurent polynomials
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• On the power of statistical zero knowledge
• The large-error approximate degree of \(\mathrm{AC}^0\)
• The large-error approximate degree of \(\mathrm{AC}^0\)
• Approximate Degree, Secret Sharing, and Concentration Phenomena
• scientific article; zbMATH DE number 7716601 (Why is no real title available?)
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
• The approximate degree of DNF and CNF formulas
• Improved hardness amplification in NP

This page was built for publication: Hardness amplification and the approximate degree of constant-depth circuits

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