Toolbox

C1: The Indexing Problem: Different Proofs (3)

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.