13
$\begingroup$

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.

$\endgroup$
17
$\begingroup$

A linear lower bound on deterministic CC follows by fixing one of the sets to be empty.

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Warren Schudy Oct 15 '10 at 18:25
1
$\begingroup$

I'm looking into a slightly different question, which seems related. What would be a good reference for details about the randomized upper bound in the above answer?

$\endgroup$
  • 1
    $\begingroup$ maybe you should post another question ? $\endgroup$ – Suresh Venkat Dec 17 '10 at 6:59
  • $\begingroup$ For the answer to my problem, you can look at the randomized protocol to solve the Equality problem to get an idea. For example, Example 3.5 in Nissan-Kushilevitz's book. The main idea is to use fingerprinting, I guess. $\endgroup$ – Danu Dec 17 '10 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.