# communication complexity lower bound for computing median

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?

• Isn't there a trivial $\Omega(\log n)$ lower bound because there are $n$ possible outputs? – Jan Johannsen Nov 29 '19 at 9:42
• 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 Nov 29 '19 at 11:18
• That is correct. – Jan Johannsen Nov 29 '19 at 13:07