11
$\begingroup$

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.

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

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

$\endgroup$
6
  • $\begingroup$ 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... $\endgroup$ – Clement C. Dec 30 '20 at 3:46
  • 1
    $\begingroup$ 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) $\endgroup$ – Clement C. Dec 30 '20 at 4:07
  • $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Dec 30 '20 at 4:42
  • $\begingroup$ @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. $\endgroup$ – Clement C. Dec 30 '20 at 4:53
  • 1
    $\begingroup$ 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. $\endgroup$ – chax Dec 30 '20 at 4:57
3
$\begingroup$

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.

$\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.