Complexity of two-party maximum Given function $\max\colon \{0, 1\}^{n} \times \{0, 1\}^{n} \rightarrow \{0, 1\}^{n}$ that returns the maximum of two binary $n$-vectors (interpreted as encoding numbers in the range $0,\ldots,2^n-1$), find a communication protocol for two parties having vectors $x$ and $y$ such that both parties will get the vector $\max(x, y)$.
It's easy to get trivial bounds for the complexity of any protocol for maximum: $n \leq \texttt{CC}(\max) \leq 2n$, but how can we use only $\frac{3n}{2} + c$ bits for some constant $c$?
Write $x = (x_h,x_l)$ and $y = (y_h,y_l)$, where $x_h,y_h$ are the high-order parts.
Alice sends $x_h$ to Bob ($n/2$ bits). Bob sends Alice two bits, indicating which of the following holds: $x_h &gt; y_h$, $x_h = y_h$, $x_h &lt; y_h$. The protocol then proceeds as follows:

If $x_h &gt; y_h$, then Alice sends Bob $x_l$ ($n/2$ bits).
If $x_h &lt; y_h$, then Bob sends Alice $y$ ($n$ bits).
If $x_h = y_h$, then Alice sends Bob $x_l$, and Bob sends Alice $y_l$ ($n$ bits).

In total, at most $\frac{3}{2}n+2$ bits are sent (assuming $n$ is even).