ECCC-Report TR15-002https://eccc.weizmann.ac.il/report/2015/002Comments and Revisions published for TR15-002en-usSat, 03 Jan 2015 00:50:25 +0200
Paper TR15-002
| The Communication Complexity of Number-In-Hand Set Disjointness with No Promise |
Mark Braverman,
Rotem Oshman
https://eccc.weizmann.ac.il/report/2015/002Set 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.Sat, 03 Jan 2015 00:50:25 +0200https://eccc.weizmann.ac.il/report/2015/002