<p>In the textbook by <a href="https://dl.acm.org/citation.cfm?id=264772" rel="nofollow noreferrer">Kushilevitz/Nisan</a>, they give an <span class="math-container">$O(\log n)$</span>-bit protocol for computing the median in the standard 2-party model of communication complexity, where Alice is given a set <span class="math-container">$X \subseteq [n]$</span> and Bob is given <span class="math-container">$Y \subseteq [n]$</span> and they need to output the median of the <strong>multiset</strong> <span class="math-container">$X \cup Y$</span>.</p>

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

<blockquote>
  <p>Are there any non-trivial lower bounds known for finding the median in the 2-party model? </p>
</blockquote>

CC BY-SA 4.0
2019-11-29T09:42:36.227Z
Isn't there a trivial $\Omega(\log n)$ lower bound because there are $n$ possible outputs?
Jan Johannsen
CC BY-SA 4.0
2019-11-29T11:18:06.877Z
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?
JohnDoe
CC BY-SA 4.0
2019-11-29T13:07:23.273Z
That is correct.
Jan Johannsen
<reference-request><communication-complexity>
communication complexity lower bound for computing median
JohnDoe
# communication complexity lower bound for computing median

(Asked by: username_0 on 2019-11-29)

In the textbook by [Kushilevitz/Nisan](https://dl.acm.org/citation.cfm?id=264772), 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?

**Tags:** reference-request, communication-complexity
> **Comments:**
> **username_1**: Isn't there a trivial $\Omega(\log n)$ lower bound because there are $n$ possible outputs?  
> **username_0**: 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?  
> **username_1**: That is correct.  

---

## 0 answers

