Near-optimal lower bounds on the threshold degree and sign-rank of AC^0
DOI10.1145/3313276.3316408zbMATH Open1433.68153OpenAlexW2908172499MaRDI QIDQ5212781FDOQ5212781
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
Recommendations
communication complexityconstant-depth circuitssign-rankthreshold degreesign-representation by polynomialsunbounded-error communication
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)
Cited In (13)
- 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
- A Borsuk-Ulam lower bound for sign-rank and its applications
- Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
- Approximate Degree in Classical and Quantum Computing
- The Sign-Rank of AC$^0$
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)
