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.