# multi-party Communication complexity of "Set Partition problem"

In an application I'm considering, I need to know the communication complexity of the following problem:

Given $n$, let $S$ be the set of integers from $1$ to $n$. Alice, Bob, and Carol each receives a subset of $S$, denoted by $A$, $B$, and $C$, respectively. They want to check whether $A$, $B$ and $C$ form a partition of $S$, i.e., they are disjoint and their union is $S$.

I'm particularly interested in the case of 3 parties but other cases would be interesting as well. Note that for the case of 2 parties, the problem is equivalent to EQUALITY problem so it has $\Omega(n)$ lower bound for deterministic protocols but $O(\log n)$ upper bound for randomized protocols.

My question is whether this problem is known before. If you know any problems that might be related, I would be interested to know as well.

For a randomized logarithmic upper bound, first note that this problem can be reduced to the problem asking whether the sum of three $$3n$$-bit numbers is exactly $$2^{3n}-1$$. This one can be solved in $$O(\log n)$$ randomized communication by the players operating mod a random $$O(\log n)$$-bit prime.
• Can't you use $2^n$ bit numbers instead and get an algorithm that works in a streaming model as well? To make this work you need to also verify that the total number of items is correct, but that's easy to do. Carries destroy ones, so the sum of $n$ powers of two equals $2^{n}-1$ if and only if there's exactly one copy of each power of two. Oct 15, 2010 at 18:25