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

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 X1, . . . , Xk ⊆ {1, . . . , n}, and their goal is to determine whether or not ⋂k i=1Xi = ∅. 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 ∈ [n], some player i such that j 6∈ Xi; 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 Ω(n log k) bits of information about each other’s inputs, and this implies a communication lower bound of Ω(n log k) as well. Overall, we obtain the tight bound Θ(n log k + k) on the problem, and give a simple matching deterministic upper bound.