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-rankthreshold degreesign-representation by polynomialsunbounded-error communication

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) Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11)

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

(13)

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

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)