1
$\begingroup$

Consider a $2$-party communication model in which $A$ wish to send to $B$ an $n$-bit string. It is very easy to prove that any deterministic protocol for this problem requires $\Omega(n)$ bits to be transmitted. It is also well-known that any randomized protocol for this problem also requires $\Omega(n)$ bits to be transmitted. Although this considered to be a trivial fact, I failed to formally prove (or find a formal proof) for this. So my question is: how to show that any randomized protocol for this problem requires $\Omega(n)$ bits to be transmitted?

$\endgroup$
  • $\begingroup$ I think some definitions are missing here. What is a communication protocol? What is a deterministic protocol? What is a randomized protocol? When does a deterministic protocol solve your communication problem? When does a randomized protocol solve your communication problem? $\endgroup$ – Yuval Filmus Feb 13 '19 at 19:36
1
$\begingroup$

You haven't defined when a randomized protocol is declared to be successful, so I will assume that at the end of the protocol, Bob tells a judge what he thinks the message is, and we want that for each message $x$, the probability that Bob is correct is at least $1-\epsilon$.

Let $X$ be a random $n$-bit string, and let $\Pi$ be the corresponding transcript. Let $R$ be the randomness in the protocol (i.e., given $R$ the protocol is deterministic, and Bob's output is deterministic). Let $Y$ be Bob's output, and let $B$ be an indicator variable for the event $X=Y$.

The definition of correctness of the protocol shows that $$ \begin{align*} H(X|\Pi R) &\leq H(BX|\Pi R) \\ &= H(B|\Pi R) + H(X|\Pi RB) \\ &\leq 1 + \Pr[B=1] H(X|\Pi R,B=1) + \Pr[B=0] H(X|\Pi R,B=0) \\ &\leq 1 + 1 \cdot 0 + \epsilon \cdot n \\ &= \epsilon n + 1. \end{align*} $$ This implies that $$ H(\Pi|R) = H(X\Pi|R) - H(X|\Pi R) = H(X) - H(X|\Pi R) \geq (1-\epsilon) n - 1, $$ since $H(X\Pi | R) = H(X | R)$ (given $R$, Alice's input $X$ determines the transcript $\Pi$) and $H(X|R) = H(X)$ (since Alice's input and the randomness are independent).

We conclude that the communication complexity is at least $$ (1-\epsilon) n - 1 = \Omega(n). $$

$\endgroup$
  • $\begingroup$ Can you explain what is $h$? and how did you get the first inequality? $\endgroup$ – user91015 Feb 13 '19 at 20:35
  • $\begingroup$ It’s the binary entropy function. Take it as an exercise. You can use the chain rule together for an indicator variable for the event that Bob was correct. $\endgroup$ – Yuval Filmus Feb 13 '19 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.