Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-002 | 2nd January 2015 23:55

The Communication Complexity of Number-In-Hand Set Disjointness with No Promise


Authors: Mark Braverman, Rotem Oshman
Publication: 3rd January 2015 00:50
Downloads: 1300


Set disjointness is one of the most fundamental problems in communication complexity. In the multi-party number-in-hand version of set disjointness, $k$ players receive private inputs $X_1,\ldots,X_k\subseteq \{1,\ldots,n\}$, and their goal is to determine whether or not $\bigcap_{i = 1}^k X_i = \emptyset$. In this paper we prove a tight lower bound on the randomized communication complexity of multi-party number-in-hand set disjointness in the shared blackboard model. Our main tool is information complexity. Intuitively, in order to "become convinced" that their sets are disjoint, the players must discover, for each element $j \in [n]$, some player $i$ such that $j \not \in X_i$; this information is worth $n \log k$ bits. We are able to formalize this information and show that the players must learn a total of $\Omega(n \log k)$ bits of information about each other's inputs, and this implies a communication lower bound of $\Omega(n \log k)$ as well. Overall, we obtain the tight bound $\Theta(n\log k + k)$ on the problem, and give a simple matching deterministic upper bound.

ISSN 1433-8092 | Imprint