186 Communication Complexity — Information Terms

186.1 Overview

This module contains the information-theoretic half of the linear lower bound for set disjointness (Rao–Yehudayoff, Thm. 6.13): the special-coordinate information terms \(I(A_T : S \mid T\, A_{\lt T}\, B_{\ge T}\, \mathcal{D})\) and \(I(B_T : S \mid T\, A_{\le T}\, B_{\gt T}\, \mathcal{D})\), the fact that protocol duality swaps the two terms, and the chain-rule upper bound \(\ell \log 2 / n\) on each term for a protocol of communication \(\ell \). The declaration documented here is the shared engine behind the duality statements: a transfer lemma for conditional mutual information under the sample-space and protocol dualities.

186.2 Declarations

Theorem 186.1 Information transfer along protocol duality

✓

Let \(p\) be a protocol on the hard sample space, let \(X, X' : \Omega \to \{ 0,1\} \) be two Boolean variables and let \(Z, Z' : \Omega \to [n] \times \{ 0,1\} ^n \times \{ 0,1\} ^n\) be two conditioning variables on the hard sample \(\Omega = \texttt{HardSample}\, n\). Suppose that \(X'\) and \(Z'\) evaluated on the dual sample are \(X\) and the recoded \(Z\) on the original sample, i.e. \(X'(\sigma (\omega )) = X(\omega )\) and \(Z'(\sigma (\omega )) = \delta (Z(\omega ))\) for every \(\omega \), where \(\sigma \) is the hard-sample duality dualHardSample and \(\delta \) the conditioning recoding dualConditioningValue. Then, under the disjoint-conditioned measure \(\mu _{\mathcal D}\), the conditional mutual information between \(X'\) and the transcript of the dual protocol \(\bar p\) given \(Z'\) equals that between \(X\) and the transcript of \(p\) given \(Z\):

\[ I\bigl[X' : M_{\bar p} \mid Z' ;\ \mu _{\mathcal D}\bigr] \; =\; I\bigl[X : M_{p} \mid Z ;\ \mu _{\mathcal D}\bigr], \]

where \(M_p = \texttt{message}\, n\, p\) denotes the transcript of \(p\).