In the textbook by Kushilevitz/Nisan, they give an $O(\log n)$-bit protocol for computing the median in the standard 2-party model of communication complexity, where Alice is given a set $X \subseteq [n]$ and Bob is given $Y \subseteq [n]$ and they need to output the median of the multiset $X \cup Y$.

However, it is not mentioned whether there is any non-trivial lower bound. Thus, my question is:

Are there any non-trivial lower bounds known for finding the median in the 2-party model?

  • 3
    $\begingroup$ Isn't there a trivial $\Omega(\log n)$ lower bound because there are $n$ possible outputs? $\endgroup$ Nov 29, 2019 at 9:42
  • 1
    $\begingroup$ Oh I see. There are $\Omega(n)$ distinct outputs and hence the protocol tree must have at least $\Omega(n)$ distinct leafs, which means that we need $\Omega(n)$ distinct transcripts and hence $\Omega(\log n)$ bits, right? $\endgroup$
    – JohnDoe
    Nov 29, 2019 at 11:18
  • 1
    $\begingroup$ That is correct. $\endgroup$ Nov 29, 2019 at 13:07


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.