The large-error approximate degree of AC^0

DOI10.4086/TOC.2021.V017A007MaRDI QIDQ5158501zbMATH OpenOpenAlexFDO

Authors Mark Bun, Justin Thaler

Publication date 25 October 2021

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2021.v017a007

zbMATH Keywords

discrepancypolynomial approximationpolynomial methodsurjectivityapproximate degreedual polynomialspolynomial threshold

Mathematics Subject Classification ID

Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Theory of computing (68Qxx)

Recommendations

• The large-error approximate degree of \(\mathrm{AC}^0\)
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• On polynomial approximations to \(\mathrm{AC}^0\)
• scientific article; zbMATH DE number 6861917
• Hardness amplification and the approximate degree of constant-depth circuits

Cites work

• scientific article; zbMATH DE number 5899233 (Why is no real title available?)
• scientific article; zbMATH DE number 5568623 (Why is no real title available?)
• scientific article; zbMATH DE number 5485575 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• A linear lower bound on the unbounded error probabilistic communication complexity.
• Approximate bounded indistinguishability
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Evolvability
• Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
• Inclusion-exclusion: exact and approximate
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Learning complexity vs communication complexity
• Lower Bounds for Quantum Communication Complexity
• Majority gates vs. general weighted threshold gates
• Near-optimal secret sharing and error correcting codes in \(\mathsf{AC}^0\)
• New degree bounds for polynomial threshold functions
• On approximate majority and probabilistic time
• On the computational power of Boolean decision lists
• On the computational power of depth-2 circuits with threshold and modulo gates
• On the power of statistical zero knowledge
• Perceptrons of large weight
• Probabilistic communication complexity
• Quantum lower bounds for the collision and the element distinctness problems
• Separating AC\(^0\) from depth-2 majority circuits
• The Sign-Rank of AC$^0$
• The intersection of two halfspaces has high threshold degree
• The pattern matrix method
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• The power of asymmetry in constant-depth circuits
• The quantum query complexity of \(\mathrm{AC}^0\)
• Threshold circuits of bounded depth

Cited in

(4)

• 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\)
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees

This page was built for publication: The large-error 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 Q5158501)