The large-error approximate degree of AC^0

DOI10.4086/TOC.2021.V017A007OpenAlexW3200234314MaRDI QIDQ5158501FDOQ5158501

Authors: Mark Bun, Justin Thaler 

Publication date: 25 October 2021

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

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

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

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)

Cites Work

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

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)