ACM Symposium on Theory of Computing (STOC)

The multiparty communication complexity of set disjointness

Alexander A. Sherstov

Published May 19, 2012• 40 citations

Publisher

Abstract

We study the set disjointness problem in the number-on-the-forehead model of multiparty communication.

DOI: 10.1145/2213977.2214026

Related papers

Contributions to the study of probabilistic communication complexity classes

Ralph Bottesch

deterministic SMP protocol for the Disjointness problem . . . .

Jan 1, 20160 citations

A Note on the Communication Complexity of Multiparty Computation in the Correlated Randomness Model

Geoffroy Couteau

Lecture notes in computer scienceJan 1, 201944 citations

A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness

Paul W. Beame, Toniann Pitassi, Nathan Segerlind +1 more

We prove that corruption, one of the most powerful measures used to analyze 2-party randomized communication complexity, satisfies a strong direct sum property under rectangular distributions. This direct sum bound holds even when the error is allowed to be exponentially close to 1. We use this to analyze the complexity of the widely-studied set disjointness problem in the usual "number-on-the-forehead" (NOF) model of multiparty communication complexity.

IEEE Conference on Computational Complexity (CCC)Jun 28, 200521 citations

Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness

Anup Rao, Amir Yehudayoff

We show that the deterministic number-on-forehead communication complexity of set disjointness for k parties on a universe of size n is Omega(n/4^k). This gives the first lower bound that is linear in n, nearly matching Grolmusz's upper bound of O(log^2(n) + k^2n/2^k). We also simplify the proof of Sherstov's Omega(sqrt(n)/(k2^k)) lower bound for the randomized communication complexity of set disjointness.

Leibniz international proceedings in informaticsJan 1, 201519 citations

Interaction in quantum communication and the complexity of set disjointness

Hartmut Klauck, Ashwin Nayak, Amnon Ta‐Shma +1 more

One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet in some scenarios there are ways of conveying information with exponentially fewer qubits than possible classically [3, 26]. Moreover, these methods have a very simple structure---they involve only few message exchanges between the communicating parties.

ACM Symposium on Theory of Computing (STOC)Jul 6, 200163 citations

Improved quantum communication complexity bounds for disjointness and equality

Peter Høyer, Ronald de Wolf

Jan 1, 20020 citations