scientific article; zbMATH DE number 7009621

DOI10.4086/toc.2018.v014a022zbMath1412.68061OpenAlexW2908449032MaRDI QIDQ4612487

Alexander A. Sherstov

Publication date: 31 January 2019

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

Full work available at URL: https://doi.org/10.4086/toc.2018.v014a022

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

PPlower boundsmultiparty communication complexityseparation of complexity classesUPPunbounded-error communication complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Approximate Degree in Classical and Quantum Computing, The hardest halfspace, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic communication complexity
• Disjointness is hard in the multiparty number-on-the-forehead model
• On the power of small-depth threshold circuits
• Halfspace matrices
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Majority gates vs. general weighted threshold gates
• Perceptrons, PP, and the polynomial hierarchy
• \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
• Robust polynomials and quantum algorithms
• The Multiparty Communication Complexity of Set Disjointness
• Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$
• The Pattern Matrix Method
• Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
• Separating ${AC}^0$ from Depth-2 Majority Circuits
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Quantum communication complexity of symmetric predicates
• Communication Complexity
• Communication Lower Bounds Using Directional Derivatives
• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
• Improved Separations between Nondeterministic and Randomized Multiparty Communication