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$
    – Wei Zhan
    Mar 12, 2021 at 20:17

0

Reset to default

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.