<p>(Reduction from set disjointness)</p>

<p>Suppose Alice and Bob are given sets $S, T \subseteq [n]$ with the guarantee
that $|S\cap T| \leq 1$. Alice and Bob run the protocol for finding the common
element of $S$ and $T$ assuming that their sets have a non-trivial intersection
to decide a common element $X$. Now, they can communicate with each other to
verify that $X$ is in fact common to both $S$ and $T$ with $O(\log n)$ bits.</p>

<p>Therefore, any protocol for finding the common element of $S$ and $T$ must take $\Omega(n)$ bits of communication.</p>

CC BY-SA 3.0
2013-08-16T23:14:35.817Z
Yes, of course, thanks!  I knew the answer should involve disjointness, but I couldn't see it.  Although, before closing the question I would like to see if anyone comments on the apparent gap between communication and zero-communication cost.
Dan Stahlke
CC BY-SA 3.0
2013-08-16T23:19:49.443Z
I am not sure what you mean by zero-communication cost. Can you provide a link or a reference?
Shitikanth
CC BY-SA 3.0
2013-08-16T23:27:05.380Z
I updated the question with a link to a paper and will also provide the definition for ZC cost.
Dan Stahlke
CC BY-SA 3.0
2013-08-17T12:44:38.640Z
Thinking it over again with a clear head, this reduction to disjointness doesn't really work.  The protocol is only required to answer with something from $S \cap T$ when $\lvert S \cap T \rvert = 1$.  And I can't modify my question to allow arbitrary $\lvert S \cap T \rvert > 1$ because I want the abort probability to be uniform.  Whether this is the root of the apparent gap between ZC and R, I don't know.
Dan Stahlke
CC BY-SA 3.0
2014-01-15T15:27:43.303Z
@DanStahlke there is a result of Razborov that the randomized communication complexity of unique set disjointness is also $\Omega(n)$
Sasho Nikolov
CC BY-SA 3.0
2013-08-16T23:04:47.473Z
2013-08-16T23:04:47.473Z
Shitikanth
<p>The decisional version of your problem can be written in the folowing form: $$EQ(s_1,t_1)\lor EQ(s_2,t_2)\lor \dots \lor EQ(s_n,t_n).$$
This is very similar to the inner product $$x_1y_1\lor x_2y_2\lor\dots\lor x_ny_n.$$
The communication complexity of those two problems is equivalent, since equality can be done at constant randomized communication cost.</p>

<p>Also, finding an $i$ such that $s_i=t_i$ is at least as hard as the decisional version of the problem. Therefore, your problem is as hard as solving $IP$ when only one clause is satisfied. I have no direct proof, but my intuition lets me believe that $IP$ with only 1 satisfied clause is as hard as general $IP$. So the randomized complexity of your problem would be in $\Theta(n)$ if I am not mistaken.</p>

<p>I hope this helps.</p>

CC BY-SA 3.0
2013-08-22T16:49:39.890Z
2013-08-22T16:49:39.890Z
lamontap
<p>Fastest protocol I can think of is alternate exchanging a random adjacent pair of elements, throwing away stuff that gets skipped over.</p>

<p>Alice[1,10,26,49,50] Bob[2,3,25,49,51]</p>

<p>Alice adjacent pair is [10,26] so Bob throws away 25</p>

<p>Alice[1,49,50] Bob[2,3,49,51]</p>

<p>Bob adjacent pair is [3,49] match on 49 so halt</p>

CC BY-SA 3.0
2013-08-16T21:55:21.880Z
2013-08-16T21:55:21.880Z
Chad Brewbaker
<p>Suppose that Alice receives a subset $S \subseteq \{1,\dots,n\}$ and Bob receives $T \subseteq \{1,\dots,n\}$.  It is promised that $\lvert S \cap T \rvert = 1$.  What is the randomized communication complexity of determining the common element $S \cap T$?</p>

<p>My interest in this is as follows.  The zero-communication cost of this problem is $\log n$ since Alice and Bob can just guess $S \cap T$ using public coins and abort if they guess wrong.  However, I can't think of an $O(\log n)$ cost communication protocol.  Since it is not known whether zero-communication cost is much less than randomized communication cost, I am thinking that I am missing something obvious here.</p>

<p>Zero-communication cost is defined as follows.  After Alice and Bob receive their inputs, they must not communicate at all.  However, they share public coins, and they are allowed to answer with "abort".  If neither party aborts, they must provide the correct answer with $2/3$ probability.  The zero-communication cost is the negative log of the probability of not aborting.  In <a href="http://arxiv.org/abs/1204.1505">arxiv:1204.1505</a> it is shown (among other things) that nearly all known lower bounds on communication complexity are in fact lower bounds for zero-communication.</p>

<p>Update: @Shitikanth showed that the communication complexity is $\Omega(n)$.  So, apparently this gives a gap between communication cost and zero-communication cost.  But <a href="http://arxiv.org/abs/1204.1505">arxiv:1204.1505</a> seems to give the impression that no such gap is known.  What am I missing?</p>

CC BY-SA 3.0
2013-08-16T23:40:15.000Z
"Alice and Bob can just guess $S\cap T$ using public coins and abort if they guess wrong." I don't think that their definition of Zero-Communication protocols allows Alice and Bob to abort after guessing. If both of them choose to answer, they must win with high probability.
Shitikanth
CC BY-SA 3.0
2013-08-17T00:14:52.827Z
Sorry for the sloppy language.  To clarify, they choose $i \in \{1,\dots,n\}$ using public coins.  Alice aborts if $i \not\in S$ and Bob aborts if $i \not\in T$.  If neither party aborts, they answer $i$.  This sort of gimmick is sometimes referred to as "guessing".
Dan Stahlke
CC BY-SA 3.0
2013-08-17T07:32:56.177Z
I see what you mean now. However, that is only one possible zero-communication protocol for this problem. The authors describe another protocol that would abort with probability just $2^{-O(n)}$.
Shitikanth
CC BY-SA 3.0
2013-08-17T12:39:47.793Z
arxiv:1204.1505 shows that the cost of any possible zero-communication (ZC) protocol with uniform (over the inputs) abort probability is lower bounded by nearly all known techniques used to lower bound communication cost.  The protocol I mention has cost $\log n$.
Dan Stahlke
<communication-complexity>
Communication complexity of finding common element of two subsets
Dan Stahlke
# Communication complexity of finding common element of two subsets

(Asked by: username_0 on 2013-08-16)

Suppose that Alice receives a subset $S \subseteq \{1,\dots,n\}$ and Bob receives $T \subseteq \{1,\dots,n\}$. It is promised that $\lvert S \cap T \rvert = 1$. What is the randomized communication complexity of determining the common element $S \cap T$?

My interest in this is as follows. The zero-communication cost of this problem is $\log n$ since Alice and Bob can just guess $S \cap T$ using public coins and abort if they guess wrong. However, I can't think of an $O(\log n)$ cost communication protocol. Since it is not known whether zero-communication cost is much less than randomized communication cost, I am thinking that I am missing something obvious here.

Zero-communication cost is defined as follows. After Alice and Bob receive their inputs, they must not communicate at all. However, they share public coins, and they are allowed to answer with "abort". If neither party aborts, they must provide the correct answer with $2/3$ probability. The zero-communication cost is the negative log of the probability of not aborting. In [arxiv:1204.1505](http://arxiv.org/abs/1204.1505) it is shown (among other things) that nearly all known lower bounds on communication complexity are in fact lower bounds for zero-communication.

Update: @username_1 showed that the communication complexity is $\Omega(n)$. So, apparently this gives a gap between communication cost and zero-communication cost. But [arxiv:1204.1505](http://arxiv.org/abs/1204.1505) seems to give the impression that no such gap is known. What am I missing?

**Tags:** communication-complexity

> **Comments:**
> **username_1**: "Alice and Bob can just guess $S\cap T$ using public coins and abort if they guess wrong." I don't think that their definition of Zero-Communication protocols allows Alice and Bob to abort after guessing. If both of them choose to answer, they must win with high probability.  
> **username_0**: Sorry for the sloppy language.  To clarify, they choose $i \in \{1,\dots,n\}$ using public coins.  Alice aborts if $i \not\in S$ and Bob aborts if $i \not\in T$.  If neither party aborts, they answer $i$.  This sort of gimmick is sometimes referred to as "guessing".  
> **username_1**: I see what you mean now. However, that is only one possible zero-communication protocol for this problem. The authors describe another protocol that would abort with probability just $2^{-O(n)}$.  
> **username_0**: arxiv:1204.1505 shows that the cost of any possible zero-communication (ZC) protocol with uniform (over the inputs) abort probability is lower bounded by nearly all known techniques used to lower bound communication cost.  The protocol I mention has cost $\log n$.  

---

## 3 answers

### Answer by username_1 on 2013-08-16. Score: 5

(Reduction from set disjointness)

Suppose Alice and Bob are given sets $S, T \subseteq [n]$ with the guarantee
that $|S\cap T| \leq 1$. Alice and Bob run the protocol for finding the common
element of $S$ and $T$ assuming that their sets have a non-trivial intersection
to decide a common element $X$. Now, they can communicate with each other to
verify that $X$ is in fact common to both $S$ and $T$ with $O(\log n)$ bits.

Therefore, any protocol for finding the common element of $S$ and $T$ must take $\Omega(n)$ bits of communication.

> **Comments:**
> **username_0**: Yes, of course, thanks!  I knew the answer should involve disjointness, but I couldn't see it.  Although, before closing the question I would like to see if anyone comments on the apparent gap between communication and zero-communication cost.  
> **username_1**: I am not sure what you mean by zero-communication cost. Can you provide a link or a reference?  
> **username_0**: I updated the question with a link to a paper and will also provide the definition for ZC cost.  
> **username_0**: Thinking it over again with a clear head, this reduction to disjointness doesn't really work.  The protocol is only required to answer with something from $S \cap T$ when $\lvert S \cap T \rvert = 1$.  And I can't modify my question to allow arbitrary $\lvert S \cap T \rvert > 1$ because I want the abort probability to be uniform.  Whether this is the root of the apparent gap between ZC and R, I don't know.  
> **username_2**: @DanStahlke there is a result of Razborov that the randomized communication complexity of unique set disjointness is also $\Omega(n)$  

---

### Answer by username_3 on 2013-08-22. Score: 1

The decisional version of your problem can be written in the folowing form: $$EQ(s\_1,t\_1)\lor EQ(s\_2,t\_2)\lor \dots \lor EQ(s\_n,t\_n).$$
This is very similar to the inner product $$x\_1y\_1\lor x\_2y\_2\lor\dots\lor x\_ny\_n.$$
The communication complexity of those two problems is equivalent, since equality can be done at constant randomized communication cost.

Also, finding an $i$ such that $s\_i=t\_i$ is at least as hard as the decisional version of the problem. Therefore, your problem is as hard as solving $IP$ when only one clause is satisfied. I have no direct proof, but my intuition lets me believe that $IP$ with only 1 satisfied clause is as hard as general $IP$. So the randomized complexity of your problem would be in $\Theta(n)$ if I am not mistaken.

I hope this helps.


---

### Answer by username_4 on 2013-08-16. Score: -3

Fastest protocol I can think of is alternate exchanging a random adjacent pair of elements, throwing away stuff that gets skipped over.

Alice[1,10,26,49,50] Bob[2,3,25,49,51]

Alice adjacent pair is [10,26] so Bob throws away 25

Alice[1,49,50] Bob[2,3,49,51]

Bob adjacent pair is [3,49] match on 49 so halt


---

