8
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ "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. $\endgroup$ – Shitikanth Aug 16 '13 at 23:40
  • 1
    $\begingroup$ 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". $\endgroup$ – Dan Stahlke Aug 17 '13 at 0:14
  • $\begingroup$ 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)}$. $\endgroup$ – Shitikanth Aug 17 '13 at 7:32
  • $\begingroup$ 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$. $\endgroup$ – Dan Stahlke Aug 17 '13 at 12:39
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dan Stahlke Aug 16 '13 at 23:14
  • $\begingroup$ I am not sure what you mean by zero-communication cost. Can you provide a link or a reference? $\endgroup$ – Shitikanth Aug 16 '13 at 23:19
  • $\begingroup$ I updated the question with a link to a paper and will also provide the definition for ZC cost. $\endgroup$ – Dan Stahlke Aug 16 '13 at 23:27
  • $\begingroup$ 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. $\endgroup$ – Dan Stahlke Aug 17 '13 at 12:44
  • 2
    $\begingroup$ @DanStahlke there is a result of Razborov that the randomized communication complexity of unique set disjointness is also $\Omega(n)$ $\endgroup$ – Sasho Nikolov Jan 15 '14 at 15:27
1
$\begingroup$

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.

$\endgroup$
-3
$\begingroup$

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

$\endgroup$

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.