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

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=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

• 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
• @SashoNikolov Ok, I guess something like this can be used as a "noisy binary search", which tolerates a constant fraction of errors so that we can use constant error probability in the equality tests: dl.acm.org/citation.cfm?id=167129 – Grigory Yaroslavtsev May 2 '13 at 22:00
• true. I meant binary search where each comparison can give the wrong result with small constant probability. I think this paper gives the needed result, for example: dl.acm.org/citation.cfm?id=100230 – Sasho Nikolov May 2 '13 at 22:01
• Moved the discussion into the answer. – Grigory Yaroslavtsev May 3 '13 at 18:07

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.