We have 2 binary strings: X and Y, in 2 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 Xi=Yi. 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?