The multiparty communication complexity of set disjointness
The paper presents in great detail and with an extended bibliography an important and recent result in communication complexity theory, and many of its consequences. Any reader interested in knowing more about fundamental questions in communication complexity, or about the innovative technique used to obtain this result, called the pattern matrix method, will greatly benefit from reading this clear, well-organized and pedagogic paper.NEWLINENEWLINECommunication complexity theory studies the amount of data that needs to be exchanged between nodes to compute a function. It completely ignores space and time complexity, to focus on the cost of sending and receiving messages. This field of study was invented in the early 80s, impacted many aspects of theoretical computer science, and gave rise to many interesting problems and techniques. The disjointness problem (determining if all the nodes have a piece of data in common) in a multiparty communication environment (i.e., when more than 2 nodes are involved) is a relatively old, central and well-studied problem. This paper offers a new lower bound for particular instances of that problem, as well as a proof of the so-called ``direct product theorem that concerns the communication needed to solve multiple instances of that problem.NEWLINENEWLINEThis paper uses a technique invented by the author, called the the pattern matrix method. How it works, why it improves on previous results, and some of its applications, are explained in great detail, making the paper extremely enjoyable to read, as well as inspiring. It is a well-crafted paper, including numerous and detailed references to previous bounds and analyses of that problem, and technically solid and convincing.
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- 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
- 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?)
- 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 cost of the missing bit: Communication complexity with help
- The pattern matrix method
- The Probabilistic Communication Complexity of Set Intersection
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- A note on multiparty communication complexity and the Hales-Jewett theorem
- On multi-partition communication complexity
- The hardest halfspace
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
- Communication complexity of set-disjointness for all probabilities
- Communication complexity theory: thirty-five years of set disjointness
- scientific article; zbMATH DE number 6696541 (Why is no real title available?)
- The randomized communication complexity of set disjointness
- The pattern matrix method
- The Simultaneous Communication of Disjointness with Applications to Data Streams
- Partition Arguments in Multiparty Communication Complexity
- Hadamard tensors and lower bounds on multiparty communication complexity
- The Probabilistic Communication Complexity of Set Intersection
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- The power of asymmetry in constant-depth circuits
- Simplified lower bounds on the multiparty communication complexity of disjointness
- Separation of unbounded-error models in multi-party communication complexity
- On multiparty communication with large versus unbounded error
- scientific article; zbMATH DE number 1419257 (Why is no real title available?)
- Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
- The communication complexity of the inevitable intersection problem
- An exponential separation between MA and AM proofs of proximity
- Simultaneous multiparty communication protocols for composed functions
- Algorithmic Polynomials
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness
- scientific article; zbMATH DE number 6292585 (Why is no real title available?)
- The multiparty communication complexity of set disjointness
- Communication lower bounds using directional derivatives
- Automata, Languages and Programming
- Inner product and set disjointness: beyond logarithmically many parties
- scientific article; zbMATH DE number 7650118 (Why is no real title available?)
- Disjointness is hard in the multiparty number-on-the-forehead model
- The approximate degree of DNF and CNF formulas
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)
