The multiparty communication complexity of set disjointness

DOI10.1137/120891587MaRDI QIDQ2817790zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• The multiparty communication complexity of set disjointness
• Simplified lower bounds on the multiparty communication complexity of disjointness
• The pattern matrix method
• Communication complexity theory: thirty-five years of set disjointness
• Communication lower bounds using directional derivatives

Cites work

• scientific article; zbMATH DE number 5953454 (Why is no real title available?)
• scientific article; zbMATH DE number 5568623 (Why is no real title available?)
• scientific article; zbMATH DE number 1512076 (Why is no real title available?)
• scientific article; zbMATH DE number 5485573 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• A separation of NP and conp in multiparty communication complexity
• A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
• A strong direct product theorem for disjointness
• An information statistics approach to data stream and communication complexity
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Communication Complexity
• Communication lower bounds using directional derivatives
• Complexity measures and decision tree complexity: a survey.
• Disjointness is hard in the multiparty number-on-the-forehead model
• Improved separations between nondeterministic and randomized multiparty communication
• Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
• Lower bounds in communication complexity based on factorization norms
• Multiparty communication complexity and threshold circuit size of AC^0
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On the computational power of depth-2 circuits with threshold and modulo gates
• On the degree of Boolean functions as real polynomials
• On the distributional complexity of disjointness
• On the power of small-depth threshold circuits
• One-way multiparty communication lower bound for pointer jumping with applications
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Quantum communication complexity of symmetric predicates
• Quantum lower bounds by polynomials
• Separating AC\(^0\) from depth-2 majority circuits
• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
• Separating deterministic from randomized multiparty communication complexity
• Simplified lower bounds on the multiparty communication complexity of disjointness
• The BNS lower bound for multi-party protocols is nearly optimal
• The Probabilistic Communication Complexity of Set Intersection
• The cost of the missing bit: Communication complexity with help
• The pattern matrix method
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom

Cited in

(35)

• Separation of unbounded-error models in multi-party communication complexity
• On multiparty communication with large versus unbounded error
• An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
• The hardest halfspace
• Algorithmic Polynomials
• A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
• scientific article; zbMATH DE number 1419257 (Why is no real title available?)
• scientific article; zbMATH DE number 6292585 (Why is no real title available?)
• The power of asymmetry in constant-depth circuits
• Simplified lower bounds on the multiparty communication complexity of disjointness
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
• Disjointness is hard in the multiparty number-on-the-forehead model
• Inner product and set disjointness: beyond logarithmically many parties
• An exponential separation between MA and AM proofs of proximity
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• scientific article; zbMATH DE number 6696541 (Why is no real title available?)
• Partition Arguments in Multiparty Communication Complexity
• The pattern matrix method
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• A note on multiparty communication complexity and the Hales-Jewett theorem
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Communication lower bounds using directional derivatives
• Communication complexity of set-disjointness for all probabilities
• Hadamard tensors and lower bounds on multiparty communication complexity
• Simultaneous multiparty communication protocols for composed functions
• The approximate degree of DNF and CNF formulas
• Communication complexity theory: thirty-five years of set disjointness
• The multiparty communication complexity of set disjointness
• The communication complexity of the inevitable intersection problem
• The Probabilistic Communication Complexity of Set Intersection
• On multi-partition communication complexity
• Automata, Languages and Programming
• The randomized communication complexity of set disjointness
• The Simultaneous Communication of Disjointness with Applications to Data Streams
• Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness

This page was built for publication: The multiparty communication complexity of set disjointness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817790)