<p>If you look at the MNSW proof carefully, the base case can be taken to be the trivial fact that a <span class="math-container">$0$</span>-round protocol for <span class="math-container">$\textrm{GT}_n$</span> with <span class="math-container">$n = 1$</span> requires one bit of communication.</p>
<p>If the goal is simply to convince oneself from first principles that <span class="math-container">$\textrm{R}^\to(\textrm{GT}_n) = \Omega(n)$</span>, this is immediate by reduction from the AUGMENTED-INDEX problem. An <span class="math-container">$\Omega(n)$</span> one-way lower bound for AUG-INDEX boils down to the chain rule for mutual information. For a discussion of AUG-INDEX, see, e.g., Section 3.4 of Jelani Nelson's PhD thesis (<a href="https://people.eecs.berkeley.edu/%7Eminilek/publications/papers/phd_thesis.pdf" rel="noreferrer">https://people.eecs.berkeley.edu/~minilek/publications/papers/phd_thesis.pdf</a>).</p>

CC BY-SA 4.0
2020-12-30T03:46:54.777Z
Regarding the first point, I don't see how that goes? Plugging $k=1$ in the argument, we get "a $[1, n/120,n/10]$ for $\mathrm{GT}_n$ implies [...] a $[0,n,n]$ protocol for $\mathrm{GT}_1$". That does lead to a contradiction (since the way it's defined, a $0$-round protocol is impossible: 0 messages), but is that a valid base case in the induction? Because in that case I can start at $k=0$ with $[0,2^{2^n},2^{2^n}]$ if I want -- still impossible...
Clement C.
CC BY-SA 4.0
2020-12-30T04:07:58.567Z
Also, for Augmented-Index, doesn't Jelani's thesis refer to the MNSW paper for the proof? (there is a self-contained bound in a 2014 paper of Feldman and Xiao, though: arxiv.org/abs/1402.6278), using mutual information as you point out)
Clement C.
CC BY-SA 4.0
2020-12-30T04:42:41.380Z
Thanks, it’s true that starting from Augmented Index makes the lower bound trivial. The MNSW proof still puzzles me a little, but I guess the round elimination lemma contains a lower bound for augmented index as a special case. @ClementC the point seems to be that the $n$ in $[0,n,n]$ and the $n$ in $\mathrm{GT}_n$ are tied together.
Sasho Nikolov
CC BY-SA 4.0
2020-12-30T04:53:32.080Z
@SashoNikolov I again am not sure -- maybe I am misunderstanding what is written, but if they are linked together the proof doesn't really make sense to me. I.e., you would need $[k-1, n^{1/(k-1)}/120^{k-1} , n^{1/(k-1)}/120^{k-1} ]$ in what is written after _"Using  the  round  elimination  lemma  this  implies  a"_ not $[k-1, n^{1/k}/120^{k-1} , n^{1/k}/120^{k-1} ]$ -- and the last part of the sentence linking $n'$ to $n$ to get the contradiction would be redundant.
Clement C.
CC BY-SA 4.0
2020-12-30T04:57:32.780Z
Don't go by the literal statement inside the proof of Theorem 19 (JCSS version of the paper), instead look at Lemma 13 and notice how $m$ and $a$ must be related in order to apply that lemma.
chax
CC BY-SA 4.0
2020-12-30T05:18:32.810Z
Oh, shoot. The jounal version has restrictions on the parameters (I was only looking at the non-paywalled version linked in the post -- where that's lemma 11, which doesn't have any (?)) @chax
Clement C.
CC BY-SA 4.0
2020-12-30T03:35:48.210Z
2020-12-30T03:35:48.210Z
chax
<p>The Ph.D. thesis of Pranab Sen (<a href="http://www.tcs.tifr.res.in/%7Epgdsen/pages/phdthesis/thesis.pdf" rel="nofollow noreferrer">http://www.tcs.tifr.res.in/~pgdsen/pages/phdthesis/thesis.pdf</a>) provides a <span class="math-container">$\Omega(n^{1/t}t^{-2})$</span> lower bound for <span class="math-container">$t$</span> round bounded error CC for Greater-than. I think the proof covers the case when <span class="math-container">$t=1$</span>.</p>
<p>In addition, there is a <span class="math-container">$\Omega(n^{1/t}t^{-3})$</span> for quantum CC in the same thesis.</p>

CC BY-SA 4.0
2020-12-30T17:50:35.760Z
2020-12-30T17:50:35.760Z
withhighprob
<p>Let <span class="math-container">$\mathrm{GT}_n:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$</span> be the greater than function: <span class="math-container">$\mathrm{GT}_n(x,y)=1$</span> exactly when the positive integer whose binary representation is <span class="math-container">$x$</span> is greater than the positive integer whose binary representation is <span class="math-container">$y$</span>.</p>
<p>It is well-known that the randomized communication complexity of <span class="math-container">$\mathrm{GT}_n$</span> is <span class="math-container">$\Theta(\log n)$</span>. Several references claim that the randomized <em>one-way</em> communication complexity of <span class="math-container">$\mathrm{GT}_n$</span> is <span class="math-container">$\Theta(n)$</span>, but I am unable to find a reference that actually contains a proof. It is easy to show a <span class="math-container">$\Omega(n/\log n)$</span> lower bound by a reduction from INDEX, and this is done in a paper by <a href="http://www.eng.tau.ac.il/%7Edanar/Public-pdf/KNR-fix.pdf" rel="noreferrer">Kremer, Nisan, and Ron</a>. They also claim that the proof of the <span class="math-container">$\Omega(n)$</span> lower bound appears in a paper by <a href="https://www.brics.dk/RS/94/41/BRICS-RS-94-41.pdf" rel="noreferrer">Miltersen, Nisan, Safra, and Wigderson</a>. The latter paper uses a round-elimination lemma to show a <span class="math-container">$\frac{n^{1/k}}{120^k}$</span> lower bound on the <span class="math-container">$k$</span>-round communication complexity of <span class="math-container">$\mathrm{GT}_n$</span> but never gets around to proving the base case somehow (see Theorem 14), and the base case is all I am asking for. They also claim this is an unpublished result of Yao, but as far as I know that result may never have been written down.</p>
<p>Surely at some point someone wrote down a proof of this lower bound? The closest I could find (with help from Clément Canonne) is <a href="https://arxiv.org/abs/1611.08946" rel="noreferrer">this paper</a> showing a lower bound on the quantum one-way communication complexity of <span class="math-container">$\mathrm{GT}_n$</span> and that just seems like an overkill.</p>

CC BY-SA 4.0
2020-12-29T21:26:34.940Z
Can you email Andrew Yao?
Turbo
CC BY-SA 4.0
2020-12-29T22:21:37.497Z
lol good one, but maybe I will pass on emailing Yao to dig out something from over 26 years ago. if anything I might email MNSW to ask where the base case of their induction went. but this seems so basic, someone must've actually written down a proof?
Sasho Nikolov
CC BY-SA 4.0
2020-12-29T23:29:02.773Z
A few papers (including MNSW) also reference the (Rusian) Master's Thesis of D.V. Smirnov (1988) for the round-complexity tradeoff, but unfortunately it is nowhere to be found (even if one does speak Russian): https://cstheory.stackexchange.com/questions/27732/reference-for-unpublished-but-quoted-manuscript
Clement C.
CC BY-SA 4.0
2020-12-30T02:17:34.393Z
Ask one of the younger folks that work in communication complexity? How about asking Anup Rao at UW or perhaps even Noam Nisan who wrote the book?
Chandra Chekuri
CC BY-SA 4.0
2020-12-30T04:45:58.683Z
@ChandraChekuri seems one of the younger CC folks wrote an answer here :)
Sasho Nikolov
CC BY-SA 4.0
2020-12-30T05:26:20.133Z
Amit will be flattered I assume :).
Chandra Chekuri
<reference-request><communication-complexity>
One-way randomized communication complexity of Greater-Than
Sasho Nikolov
# One-way randomized communication complexity of Greater-Than

(Asked by: username_0 on 2020-12-29)

Let $\mathrm{GT}\_n:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ be the greater than function: $\mathrm{GT}\_n(x,y)=1$ exactly when the positive integer whose binary representation is $x$ is greater than the positive integer whose binary representation is $y$.

It is well-known that the randomized communication complexity of $\mathrm{GT}\_n$ is $\Theta(\log n)$. Several references claim that the randomized *one-way* communication complexity of $\mathrm{GT}\_n$ is $\Theta(n)$, but I am unable to find a reference that actually contains a proof. It is easy to show a $\Omega(n/\log n)$ lower bound by a reduction from INDEX, and this is done in a paper by [Kremer, Nisan, and Ron](http://www.eng.tau.ac.il/%7Edanar/Public-pdf/KNR-fix.pdf). They also claim that the proof of the $\Omega(n)$ lower bound appears in a paper by [Miltersen, Nisan, Safra, and Wigderson](https://www.brics.dk/RS/94/41/BRICS-RS-94-41.pdf). The latter paper uses a round-elimination lemma to show a $\frac{n^{1/k}}{120^k}$ lower bound on the $k$-round communication complexity of $\mathrm{GT}\_n$ but never gets around to proving the base case somehow (see Theorem 14), and the base case is all I am asking for. They also claim this is an unpublished result of Yao, but as far as I know that result may never have been written down.

Surely at some point someone wrote down a proof of this lower bound? The closest I could find (with help from Clément Canonne) is [this paper](https://arxiv.org/abs/1611.08946) showing a lower bound on the quantum one-way communication complexity of $\mathrm{GT}\_n$ and that just seems like an overkill.

**Tags:** reference-request, communication-complexity
> **Comments:**
> **username_1**: Can you email Andrew Yao?  
> **username_0**: lol good one, but maybe I will pass on emailing Yao to dig out something from over 26 years ago. if anything I might email MNSW to ask where the base case of their induction went. but this seems so basic, someone must've actually written down a proof?  
> **username_2**: A few papers (including MNSW) also reference the (Rusian) Master's Thesis of D.V. Smirnov (1988) for the round-complexity tradeoff, but unfortunately it is nowhere to be found (even if one does speak Russian): https://cstheory.stackexchange.com/questions/27732/reference-for-unpublished-but-quoted-manuscript  
> **username_3**: Ask one of the younger folks that work in communication complexity? How about asking Anup Rao at UW or perhaps even Noam Nisan who wrote the book?  
> **username_0**: @ChandraChekuri seems one of the younger CC folks wrote an answer here :)  
> **username_3**: Amit will be flattered I assume :).  

---

## 2 answers

### Answer by username_4 on 2020-12-30. Score: 7 | Accepted answer

If you look at the MNSW proof carefully, the base case can be taken to be the trivial fact that a $0$-round protocol for $\textrm{GT}\_n$ with $n = 1$ requires one bit of communication.

If the goal is simply to convince oneself from first principles that $\textrm{R}^\to(\textrm{GT}\_n) = \Omega(n)$, this is immediate by reduction from the AUGMENTED-INDEX problem. An $\Omega(n)$ one-way lower bound for AUG-INDEX boils down to the chain rule for mutual information. For a discussion of AUG-INDEX, see, e.g., Section 3.4 of Jelani Nelson's PhD thesis ([https://people.eecs.berkeley.edu/~minilek/publications/papers/phd\_thesis.pdf](https://people.eecs.berkeley.edu/%7Eminilek/publications/papers/phd_thesis.pdf)).

> **Comments:**
> **username_2**: Regarding the first point, I don't see how that goes? Plugging $k=1$ in the argument, we get "a $[1, n/120,n/10]$ for $\mathrm{GT}_n$ implies [...] a $[0,n,n]$ protocol for $\mathrm{GT}_1$". That does lead to a contradiction (since the way it's defined, a $0$-round protocol is impossible: 0 messages), but is that a valid base case in the induction? Because in that case I can start at $k=0$ with $[0,2^{2^n},2^{2^n}]$ if I want -- still impossible...  
> **username_2**: Also, for Augmented-Index, doesn't Jelani's thesis refer to the MNSW paper for the proof? (there is a self-contained bound in a 2014 paper of Feldman and Xiao, though: arxiv.org/abs/1402.6278), using mutual information as you point out)  
> **username_0**: Thanks, it’s true that starting from Augmented Index makes the lower bound trivial. The MNSW proof still puzzles me a little, but I guess the round elimination lemma contains a lower bound for augmented index as a special case. @ClementC the point seems to be that the $n$ in $[0,n,n]$ and the $n$ in $\mathrm{GT}_n$ are tied together.  
> **username_2**: @SashoNikolov I again am not sure -- maybe I am misunderstanding what is written, but if they are linked together the proof doesn't really make sense to me. I.e., you would need $[k-1, n^{1/(k-1)}/120^{k-1} , n^{1/(k-1)}/120^{k-1} ]$ in what is written after _"Using  the  round  elimination  lemma  this  implies  a"_ not $[k-1, n^{1/k}/120^{k-1} , n^{1/k}/120^{k-1} ]$ -- and the last part of the sentence linking $n'$ to $n$ to get the contradiction would be redundant.  
> **username_4**: Don't go by the literal statement inside the proof of Theorem 19 (JCSS version of the paper), instead look at Lemma 13 and notice how $m$ and $a$ must be related in order to apply that lemma.  
> **username_2**: Oh, shoot. The jounal version has restrictions on the parameters (I was only looking at the non-paywalled version linked in the post -- where that's lemma 11, which doesn't have any (?)) @chax  

---

### Answer by username_5 on 2020-12-30. Score: 3

The Ph.D. thesis of Pranab Sen ([http://www.tcs.tifr.res.in/~pgdsen/pages/phdthesis/thesis.pdf](http://www.tcs.tifr.res.in/%7Epgdsen/pages/phdthesis/thesis.pdf)) provides a $\Omega(n^{1/t}t^{-2})$ lower bound for $t$ round bounded error CC for Greater-than. I think the proof covers the case when $t=1$.

In addition, there is a $\Omega(n^{1/t}t^{-3})$ for quantum CC in the same thesis.


---

