14
$\begingroup$

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.

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ 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? $\endgroup$ – Joshua Grochow May 2 '13 at 20:56
  • $\begingroup$ @JoshuaGrochow I think that depends on the nature of randomness - public or private. The protocol you mention uses public randomness. $\endgroup$ – Sasho Nikolov May 2 '13 at 21:20
  • 1
    $\begingroup$ 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. $\endgroup$ – András Salamon May 3 '13 at 19:15
  • 1
    $\begingroup$ 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? $\endgroup$ – user6973 May 5 '13 at 8:45
  • 1
    $\begingroup$ 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 :) $\endgroup$ – Marc Bury May 23 '13 at 8:28
11
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 5
    $\begingroup$ 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 $\endgroup$ – Sasho Nikolov May 2 '13 at 21:27
  • 2
    $\begingroup$ 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. $\endgroup$ – Grigory Yaroslavtsev May 2 '13 at 21:34
  • 2
    $\begingroup$ @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 $\endgroup$ – Grigory Yaroslavtsev May 2 '13 at 22:00
  • 1
    $\begingroup$ 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 $\endgroup$ – Sasho Nikolov May 2 '13 at 22:01
  • $\begingroup$ Moved the discussion into the answer. $\endgroup$ – Grigory Yaroslavtsev May 3 '13 at 18:07
7
$\begingroup$

See The communication complexity of addition.

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.