This question comes from what I asked in a comment here, although I realized that I don't actually care about which input is less than the other, if they're different.

Alice and Bob have n-bit strings, and want to figure out if they're equal while doing little communication. $\:$ They can use a randomized solution, but there must be zero chance of getting the wrong answer.

Parametrized by $n$, how much communication is needed to for a protocol that:

  • outputs one of {NO,MAYBE,YES}
  • for all input pairs, the probability of the protocol outputting MAYBE on that pair is at most 1/2
  • the protocol never outputs YES on unequal inputs, and never outputs NO on equal inputs ?

Since this falls between the deterministic and the standard randomized cases, the bounds for those are upper and lower bounds, respectively, for this question.


Let $D$ be the distribution on inputs that w.p. $p = 1/(1+\epsilon)$ picks $(x,x)$ for random $x$, and w.p. $1-p$ picks $(x,y)$ for random $x \neq y$. An appropriate choice of random coins leads to a deterministic protocol that never makes mistakes and outputs MAYBE w.p. at most $1/2$ with respect to $D$. In particular, it must answer YES on at least $1-(1/2)/p = 1/2 - \epsilon/2$ of the nodes $(x,x)$.

Suppose that the protocol uses $C$ bits of communications. It therefore has at most $2^C$ leaves. Each leaf is a monochromatic combinatorial rectangle, and so each of the at least $(1-\epsilon) 2^{n-1}$ YES answers must end up in a different leaf. We conclude that $C \geq n-1$.


I think that $C <= n-1$ seems a little high. If we are looking at bounds, lets assume that for a given communication $C$ the cost of the communication is at most $C=\gamma n + \Delta$, where $\gamma$ and $\Delta$ are fixed (a simple value for $\gamma$ would be 1). If $\Delta$ is the answer {YES,NO,MAYBE} then as $n$ grows the cost of $C \equiv n$. But we can also assume that $1/2$ of the time we can just answer MAYBE, which has a cost of just $\Delta$.

If on the first communication we use the normal protocol, it will cost $n$.

On the second communication we can use the MAYBE answer, this cost $\Delta$.

Over time we alternate between the two and thus we have a cost of $(n + \Delta)/2$ which approches $n/2$ as $n$ approaches infinity.

There are more complex solutions that can use hashes to reduce the communication required for inputs that don't match that can be much lower than $n/2$, depending on the likelihood that the inputs match.

  • $\begingroup$ I don't understand: the question does not mention C? $\endgroup$ – Jeremy May 13 '13 at 9:22
  • $\begingroup$ I was referring to the previous answer. $\endgroup$ – Milhous May 13 '13 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy