Alice and Bob have n-bit strings, and want to figure out if they're equal while doing little communication. The standard randomized solution is to treat the n-bit strings as polynomials of degree $n$ and then evaluate the polynomials over a few randomly chosen elements from a field of size larger than $n$. This takes $O(\log |F|)$ communication.Suppose instead that we fix a lexicographic ordering over the strings and want instead to determine which string is larger, which is equivalent to finding the leftmost bit where the strings differ. Is there a similar randomized protocol for doing this, or a known  lower bound ? This seems to relate to testing positivity of  polynomials.p.s While lexicographic order seems like the most obvious, I'm fine with other orderings: for the purpose I'm interested in, all we need is some order. 
Testing for positivity instead of equality
communication complexity;property testing
This is known as Greater-Than problem in communication complexity. An algorithm with $O(\log n) $ communication complexity exists (Exercise 3.18 in Nisan-Kushilevitz book). Edit: The algorithm is due to Nisan (page 10): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&rep=rep1&type=pdfIt uses the approach suggested by @Sasho Nikolov below --- running a binary search using equality tests with constant error to do the comparisons. This can be done with $O(\log n)$ queries using the noisy binary search algorithm by Feige, Peleg, Raghavan and Upfal: http://cs.brown.edu/~eli/papers/SICOMP23FRPU.pdf To get a (non-explicit) private randomness protocol one can apply the result of Newman: http://pdf.aminer.org/000/933/113/private_vs_common_random_bits_in_communication_complexity.pdf