# Multi-round communication complexity of greater than

For the "greater-than" problem in Yao's 2-party communication complexity model, Alice receives $$X$$ and Bob receives $$Y$$, and they need to decide whether $$X>Y$$.

I recently listened to an (online) seminar talk where the speaker mentioned that it is known that any randomized $$k$$-round protocol that computes "greater-than" requires $$\Omega\left(\frac{(\log n)^{1/k}}{k^2}\right)$$ bits.

Unfortunately, I didn't get to ask the speaker about where this result appeared and I didn't have any luck searching for it online. Is there a reference where I could find the proof for this round-communication trade-off?

• An $\Omega(\log n)$ lower bound already holds for any round. It should be $\Omega(n^{1/k}k^{-2})$ and it was proved here. (See this answer by sagnik) Mar 12 at 20:17