Near-optimal lower bounds on the threshold degree and sign-rank of AC^0

DOI10.1145/3313276.3316408MaRDI QIDQ5212781zbMATH OpenOpenAlexFDO

Authors Pei Wu, Alexander A. Sherstov

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3313276.3316408

zbMATH Keywords

communication complexityconstant-depth circuitssign-ranksign-representation by polynomialsthreshold degreeunbounded-error communication

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
• The Sign-Rank of AC^0
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Separating AC\(^0\) from depth-2 majority circuits

Cited in

(14)

• \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
• The Sign-Rank of AC^0
• Separating AC\(^0\) from depth-2 majority circuits
• The power of asymmetry in constant-depth circuits
• \(\mathrm{AC}^0\circ\mathrm{MOD}_2\) lower bounds for the Boolean inner product
• Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
• Approximate Degree in Classical and Quantum Computing
• A short list of equalities induces large sign-rank
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• Breaking the Minsky-Papert barrier for constant-depth circuits
• The large-error approximate degree of \(\mathrm{AC}^0\)
• A Borsuk-Ulam lower bound for sign-rank and its applications
• The approximate degree of DNF and CNF formulas

This page was built for publication: Near-optimal lower bounds on the threshold degree and sign-rank of \(\mathrm{AC}^0\)

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