Communication complexity of finding common element of two subsets

Question

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 it is shown (among other things) that nearly all known lower bounds on communication complexity are in fact lower bounds for zero-communication.

Update: @Shitikanth 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 seems to give the impression that no such gap is known. What am I missing?

Answer 1

(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.

Answer 2

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 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