# One-way randomized communication complexity of Greater-Than

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. They also claim that the proof of the $$\Omega(n)$$ lower bound appears in a paper by Miltersen, Nisan, Safra, and Wigderson. 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 showing a lower bound on the quantum one-way communication complexity of $$\mathrm{GT}_n$$ and that just seems like an overkill.

• Can you email Andrew Yao? – 1.. Dec 29 '20 at 21:26
• 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 Dec 29 '20 at 22:21
• 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): cstheory.stackexchange.com/questions/27732/… – Clement C. Dec 29 '20 at 23:29
• 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 Dec 30 '20 at 2:17
• @ChandraChekuri seems one of the younger CC folks wrote an answer here :) – Sasho Nikolov Dec 30 '20 at 4:45

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

• 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. Dec 30 '20 at 3:46
• 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. Dec 30 '20 at 4:07
• 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 Dec 30 '20 at 4:42
• @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. Dec 30 '20 at 4:53
• 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 Dec 30 '20 at 4:57

The Ph.D. thesis of Pranab Sen (http://www.tcs.tifr.res.in/~pgdsen/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.