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

DOI10.1145/3313276.3316408zbMath1433.68153OpenAlexW2908172499MaRDI QIDQ5212781

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)

Related Items

Approximate Degree in Classical and Quantum Computing, Unnamed Item