Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-002 | 2nd January 2015 23:55

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

RSS-Feed




TR15-002
Authors: Mark Braverman, Rotem Oshman
Publication: 3rd January 2015 00:50
Downloads: 4084
Keywords: 


Abstract:

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