Reminder: This post contains 1429 words
· 5 min read
· by Xianbin
For the previous two different proofs, please look at the second proof and the first proof.
The Third Proof
By Yao’s minimax, we only need to construct a distribution (here we use the uniform distribution
\(\mu\sim\{0,1\}^n\)) over which any deterministic algorithm cannot beat \(\Omega(n)\) with probability at most \(1/2-c\).
Let \(\Pi\) be the transcript of Alice with size \(\ell\). We know that \(\Pi\) fully depends on the string \(S\in \mu\) where \(S = S_1S_2\ldots S_n\). Notice that \(S_i \perp S_j\) for any \(i\neq j\).
\(I(\Pi: S)\leq H(\Pi) \leq \ell\).
So, we only need to prove that
\[I(\Pi: S) \geq \Omega(n)\]
Since \(S_i\perp S_j\) for any \(i\neq j\), by the chain rule, we have
\[I(\Pi:S) = \sum_{i=1}^n I(\Pi:S_i)\]
Therefore, we only need to prove that
\[I(\Pi:S_i) = \Omega(1)\]
\[I(\Pi:S_i) = H(\Pi)- H(\Pi \mid S_i) = H(S_i) - H(S_i \mid \Pi)\]
Due to the uniform distribution, \(H(S_i) = H(1/2) = 1\).
Now, let us see \(H(S_i \mid \Pi)\).
\[H(S_i \mid \Pi) = \mathbb{E}_\pi [H(S_i \mid \Pi=\pi)]\]
Let \(P_r [\Pi \text{ is wrong} \mid \text{Alice sends message pi and Bob has input i} ]= r^i_\pi\)
According to the condition, we have \(\mathbb{E}_{i,m}r^i_m \leq 1/2 -c\).
Then, by Jensen’s inequality,
\[H(S_i \mid \Pi) = \mathbb{E}_\pi [H(S_i \mid \Pi =\pi)] \leq H(\mathbb{E}_\pi[S_i\mid \Pi=\pi])\\
\leq H(\mathbb{E}_\pi[r^i_m])\]
The last one is due to Fano’s inequality. (It seems that reference [1] is wrong here.)
Consider all \(i\), we have
\[\mathbb{E}_i [H(S_i \mid \Pi)] = H(\mathbb{E}_{i,m}[r^i_m])\]
Then, we get that
\[1-H(1/2-c) = \Omega(1)\]
Then, it is proved.
Reference
[1]. Communication Complexity 16 Sep, 2011 (@ TIFR) 10. Pointer Chasing.