<p>See <a href="http://www.ccs.neu.edu/home/viola/papers/ccsum.pdf">The communication complexity of addition</a>.</p>

<p>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.</p>

CC BY-SA 3.0
2013-05-03T13:33:45.063Z
2013-05-03T13:33:45.063Z
Manu
<p>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). </p>

<p>Edit: The algorithm is due to Nisan (page 10): <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&amp;rep=rep1&amp;type=pdf">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&amp;rep=rep1&amp;type=pdf</a></p>

<p>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: <a href="http://cs.brown.edu/~eli/papers/SICOMP23FRPU.pdf">http://cs.brown.edu/~eli/papers/SICOMP23FRPU.pdf</a> </p>

<p>To get a (non-explicit) private randomness protocol one can apply the result of Newman: <a href="http://pdf.aminer.org/000/933/113/private_vs_common_random_bits_in_communication_complexity.pdf">http://pdf.aminer.org/000/933/113/private_vs_common_random_bits_in_communication_complexity.pdf</a></p>

CC BY-SA 3.0
2013-05-02T21:27:09.753Z
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
CC BY-SA 3.0
2013-05-02T21:34:49.227Z
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
CC BY-SA 3.0
2013-05-02T22:00:12.113Z
@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: http://dl.acm.org/citation.cfm?id=167129
Grigory Yaroslavtsev
CC BY-SA 3.0
2013-05-02T22:01:50.553Z
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: http://dl.acm.org/citation.cfm?id=100230
Sasho Nikolov
CC BY-SA 3.0
2013-05-03T18:07:31.023Z
Moved the discussion into the answer.
Grigory Yaroslavtsev
CC BY-SA 3.0
2013-05-02T19:38:58.813Z
2013-05-03T18:07:08.693Z
2013-05-03T18:07:08.693Z
Grigory Yaroslavtsev
<p>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.</p>

<p>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. </p>

<blockquote>
  <p>Is there a similar randomized protocol for doing this, or a known
  lower bound ? This seems to relate to testing positivity of
  polynomials.</p>
</blockquote>

<p>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 <em>some</em> order. </p>

CC BY-SA 3.0
2013-05-02T20:56:07.970Z
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
CC BY-SA 3.0
2013-05-02T21:20:41.267Z
@JoshuaGrochow I think that depends on the nature of randomness - public or private. The protocol you mention uses public randomness.
Sasho Nikolov
CC BY-SA 3.0
2013-05-03T15:05:54.207Z
@SashoNikolov: Ah, yes! Thanks for the clarification.
Joshua Grochow
CC BY-SA 3.0
2013-05-03T19:15:17.040Z
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
CC BY-SA 3.0
2013-05-04T00:04:43.600Z
@RickyDemer what is the communication complexity analog of ZPP you have in mind?
Sasho Nikolov
CC BY-SA 3.0
2013-05-04T09:10:17.043Z
@RickyDemer: The deterministic protocol where Alice sends her most significant unsent bits, one by one, to Bob, who responds with 0 or 1 as soon as this is determined, seems to have expected complexity something like $1+\sum_{i=1}^n i2^{-i}$, which is bounded above by 3.
András Salamon
CC BY-SA 3.0
2013-05-05T07:47:23.813Z
@RickyDemer: Indeed.  Do you have a more ZPP-like notion?
András Salamon
CC BY-SA 3.0
2013-05-05T18:06:53.867Z
maybe this should become a separate question in itself ?
Suresh Venkat
CC BY-SA 3.0
2013-05-15T09:13:26.527Z
See separate question: http://cstheory.stackexchange.com/questions/17529/testing-for-equality-with-zero-error
András Salamon
CC BY-SA 3.0
2013-05-23T08:28:42.150Z
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 http://arxiv.org/abs/cs/0309033. It is a nice paper :)
Marc Bury
<communication-complexity><property-testing>
Testing for positivity instead of equality
Suresh Venkat
# Testing for positivity instead of equality

(Asked by: username_0 on 2013-05-02)

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.

**Tags:** communication-complexity, property-testing

> **Comments:**
> **username_1**: 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?  
> **username_2**: @JoshuaGrochow I think that depends on the nature of randomness - public or private. The protocol you mention uses public randomness.  
> **username_1**: @SashoNikolov: Ah, yes! Thanks for the clarification.  
> **username_3**: 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.  
> **username_2**: @RickyDemer what is the communication complexity analog of ZPP you have in mind?  
> **username_3**: @RickyDemer: The deterministic protocol where Alice sends her most significant unsent bits, one by one, to Bob, who responds with 0 or 1 as soon as this is determined, seems to have expected complexity something like $1+\sum_{i=1}^n i2^{-i}$, which is bounded above by 3.  
> **username_3**: @RickyDemer: Indeed.  Do you have a more ZPP-like notion?  
> **username_0**: maybe this should become a separate question in itself ?  
> **username_3**: See separate question: http://cstheory.stackexchange.com/questions/17529/testing-for-equality-with-zero-error  
> **username_4**: 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 http://arxiv.org/abs/cs/0309033. It is a nice paper :)  

---

## 2 answers

### Answer by username_6 on 2013-05-02. Score: 11 | Accepted answer

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 @username_2 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>

> **Comments:**
> **username_2**: 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  
> **username_6**: 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.  
> **username_6**: @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: http://dl.acm.org/citation.cfm?id=167129  
> **username_2**: 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: http://dl.acm.org/citation.cfm?id=100230  
> **username_6**: Moved the discussion into the answer.  

---

### Answer by username_5 on 2013-05-03. Score: 7

See [The communication complexity of addition](http://www.ccs.neu.edu/home/viola/papers/ccsum.pdf).

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.


---

