Testing for positivity instead of equality 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.
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&amp;rep=rep1&amp;type=pdf

It 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