<p>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?</p>

CC BY-SA 2.5
2010-12-17T06:59:01.377Z
maybe you should post another question ?
Suresh Venkat
CC BY-SA 2.5
2010-12-17T23:55:01.463Z
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.
Dan
CC BY-SA 2.5
2010-12-16T21:07:12.203Z
2010-12-16T21:07:12.203Z
Keren
<p>A linear lower bound on deterministic CC follows by fixing one of the sets to be empty.</p>

<p>For a randomized logarithmic upper bound, first note that this problem can be reduced to the problem asking whether the sum of three <span class="math-container">$3n$</span>-bit numbers is exactly <span class="math-container">$2^{3n}-1$</span>.  This one can be solved in <span class="math-container">$O(\log n)$</span> randomized communication by the players operating mod a random <span class="math-container">$O(\log n)$</span>-bit prime.  </p>

CC BY-SA 2.5
2010-10-15T18:25:42.703Z
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.
Warren Schudy
CC BY-SA 4.0
2010-10-15T18:14:18.703Z
2019-01-25T08:08:36.640Z
2019-01-25T08:08:36.640Z
Noam
<p>In an application I'm considering, I need to know the communication complexity of the following problem: </p>

<p>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$. </p>

<p>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. </p>

<p>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. </p>

<cc.complexity-theory><communication-complexity>
multi-party Communication complexity of "Set Partition problem"
Dan
# multi-party Communication complexity of "Set Partition problem"

(Asked by: username_0 on 2010-10-15)

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.

**Tags:** cc.complexity-theory, communication-complexity

---

## 2 answers

### Answer by username_3 on 2010-10-15. Score: 17 | Accepted answer

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.

> **Comments:**
> **username_4**: 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.  

---

### Answer by username_1 on 2010-12-16. Score: 1

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?

> **Comments:**
> **username_2**: maybe you should post another question ?  
> **username_0**: 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.  

---

