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

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Can you email Andrew Yao? $\endgroup$
    – Turbo
    Dec 29, 2020 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, 2020 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, 2020 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, 2020 at 2:17
  • 1
    $\begingroup$ @ChandraChekuri seems one of the younger CC folks wrote an answer here :) $\endgroup$
    – Sasho Nikolov
    Dec 30, 2020 at 4:45

2 Answers 2

Reset to default
7
$\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).

Improve this answer
$\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, 2020 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, 2020 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, 2020 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, 2020 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, 2020 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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