The Multiparty Communication Complexity of Set Disjointness

DOI10.1137/120891587zbMath1393.68052OpenAlexW2514575731MaRDI QIDQ2817790

Alexander A. Sherstov

Publication date: 2 September 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/120891587

zbMATH Keywords

circuit complexitymultiparty communication complexitydirect product theoremsset disjointnesscommunication lower boundsnumber-on-the-forehead modelXOR lemmas

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 (12)

Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algorithmic Polynomials ⋮ An Exponential Separation Between MA and AM Proofs of Proximity ⋮ The hardest halfspace ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• One-way multiparty communication lower bound for pointer jumping with applications
• An information statistics approach to data stream and communication complexity
• Disjointness is hard in the multiparty number-on-the-forehead model
• On the power of small-depth threshold circuits
• The cost of the missing bit: Communication complexity with help
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On the distributional complexity of disjointness
• On the computational power of depth-2 circuits with threshold and modulo gates
• The BNS lower bound for multi-party protocols is nearly optimal
• On the degree of Boolean functions as real polynomials
• Complexity measures and decision tree complexity: a survey.
• \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
• A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
• A strong direct product theorem for 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
• The Probabilistic Communication Complexity of Set Intersection
• Quantum communication complexity of symmetric predicates
• Communication Complexity
• Strong Direct Product Theorems for Quantum Communication and Query Complexity
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
• Quantum lower bounds by polynomials
• Communication Lower Bounds Using Directional Derivatives
• Improved Separations between Nondeterministic and Randomized Multiparty Communication
• Lower bounds in communication complexity based on factorization norms

This page was built for publication: The Multiparty Communication Complexity of Set Disjointness