# 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.

• I thought the standard randomized solution was to pick a random linear combination of the bits, and just send the resulting parity, which takes only $O(1)$ communication? – Joshua Grochow May 2 '13 at 20:56
• @JoshuaGrochow I think that depends on the nature of randomness - public or private. The protocol you mention uses public randomness. – Sasho Nikolov May 2 '13 at 21:20
• For comparison, it is perhaps worth mentioning that the deterministic complexity is $n+1$, so the trivial protocol is optimal. This gives a nice exponential gap between deterministic/exact and randomized solutions, showing that (at least in communication complexity), randomness really can help. – András Salamon May 3 '13 at 19:15
• um... yeah. $\:$ How much communication is needed for an algorithm that never gives the wrong answer and, for all input pairs, gives MAYBE to that input pair with probability at most 1/2? – user6973 May 5 '13 at 8:45
• Maybe it is worth to mention that the $k$-round communication complexity of greater than is $\Omega(n^{1/k}k^{-2})$ in particular i.e. it is linear for $k=1$, see arxiv.org/abs/cs/0309033. It is a nice paper :) – Marc Bury May 23 '13 at 8:28

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).

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
• One easy solution with polylog communication is to use equality to do a binary search for the first bit where the strings differ. The $\log n$ solution is with public randomness: again use equality as an oracle, but perform each equality test with constant probability of error so that each equality call uses $O(1)$ bits; now simple binary search does not suffice, you need "noisy binary search", but there are ways to do this with log complexity – Sasho Nikolov May 2 '13 at 21:27
• Not sure what "noisy binary search" is, but you can do $O(\log n \log \log n)$ in the public randomness model by doing binary search using equality tests with error probability $O(1 / \log n)$, which requires $O(\log \log n)$ communication per test, and you get constant error probability overall by a union bound. – Grigory Yaroslavtsev May 2 '13 at 21:34
As Grigory mentioned, there is a protocol with communication $O(\log n)$. This is due to Nisan and Safra. Their protocol either uses public randomness or is not explicit. The above paper gives one that uses private randomness and is explicit (via a relatively standard use of pseudorandom generators); it also discusses matching lower bounds in the public-randomness model.