-1
$\begingroup$

We have two binary strings, $X$ and $Y$, in two different computers. Both of them in length $n$. The computers can communicate by sending bits to each other.

We have to build randomized algorithm to check whether there's an index $i$ such that $X_i=Y_i$. We can send only $O(\log n)$ bits between the computers.

If there's no such index the algorithm will always return "false". If there's such index, the algorithm will return "true" in probability 0.5 (at least).

Any suggestions?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Any suggestions? Yes: do not cross-post. It is not well regarded. You should remove one of your two posts. $\endgroup$
    – babou
    Jun 6, 2014 at 14:27

1 Answer 1

Reset to default
1
$\begingroup$

Hint: This is the classical problem of EQUALITY in disguise, a problem whose randomized communication complexity is known to be $O(\log n)$. In other words, you can reduce your problem to EQUALITY.

Improve this answer
$\endgroup$

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