Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 5 down vote favorite

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.

share|improve this question

2 Answers

up vote 9 down vote accepted

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

share|improve this answer
up vote 1 down vote

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.

share|improve this answer
I don't understand: the question does not mention C? – Jeremy May 13 at 9:22
I was referring to the previous answer. – Milhous May 13 at 13:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.