C1: The Indexing Problem: Different Proofs (3)

December 20, 2024

• The Third Proof
• Reference

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.