3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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) $\endgroup$ – Willard Zhan Mar 12 at 20:17

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.