In the multiparty set disjointness problem, we have k players, with private inputs X1,...,Xk \subseteq [n]. The players’ goal is to check whether their sets intersect, or sometimes to compute the full intersection. It is known that in the shared blackboard model of communication, set disjointness requires Omega(n log k + k) bits of communication, and in the coordinator model, it requires Omega(nk) bits. However, these two lower bounds require that the players’ inputs be highly correlated.

We study the communication complexity of multiparty set disjointness under distributions where the players' inputs have a bounded amount of dependence between them, and ask whether the problem becomes significantly easier, as it is known to become in the two party case. Our main result is a nearly-tight bound of tilde-Theta(n^{1-1/k}*d^{1/k}) bits for both the shared blackboard model and the coordinator model, where d is the amount of dependence between the inputs. This shows that in the shared blackboard model, as the number of players grows, having nearly-independent inputs helps less and less; but in the coordinator model, when k is large, having nearly-independent inputs makes the problem much easier. Both our upper and our lower bounds use new ideas, as the original techniques developed for the two-party case do not scale to more than two players.