14
$\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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Oct 15, 2010 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?

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ maybe you should post another question ? $\endgroup$
    – Suresh Venkat
    Commented Dec 17, 2010 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$
    – Dan
    Commented Dec 17, 2010 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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