62 Communication Complexity — Private Coin Approximation
62.1 Overview
This module develops the coin-approximation machinery used in Newman’s theorem. Starting from a CDF-inversion construction that approximates an arbitrary probability mass function on \(\mathrm{Fin}\, m\) by a uniform distribution over a finite coin tape, it builds up to the key result that any finite-message private-coin protocol over arbitrary finite probability spaces can be replaced by one whose randomness comes from a standard coin tape, at the cost of an additive \(\delta \) increase in error.
62.2 Declarations
Given a probability mass function \(p\) on \(\mathrm{Fin}\, m\) and a natural number \(n\), \(\mathrm{cdf}(p, n)\) is the cumulative probability \(\sum _{j \lt n} p(j)\), computed as an extended non-negative real (\(\mathbb {R}_{\ge 0}^\infty \)).
For any PMF \(p\) on \(\mathrm{Fin}\, m\), \(\mathrm{cdf}(p, 0) = 0\).
For any PMF \(p\) on \(\mathrm{Fin}\, m\) and index \(n \in \mathrm{Fin}\, m\), \(\mathrm{cdf}(p, n+1) = \mathrm{cdf}(p, n) + p(n)\).
For any PMF \(p\) on \(\mathrm{Fin}\, m\), \(\mathrm{cdf}(p, m) = 1\).
For any PMF \(p\) on \(\mathrm{Fin}\, m\), the function \(n \mapsto \mathrm{cdf}(p, n)\) is monotone non-decreasing.
Given a PMF \(p\) on \(\mathrm{Fin}\, m\) (with \(m \ge 1\)) and a value \(x \in \mathbb {R}_{\ge 0}^\infty \), \(\mathrm{invCdf}(p, x)\) is the largest index \(i \in \mathrm{Fin}\, m\) satisfying \(\mathrm{cdf}(p, i) \le x\), i.e. the generalized inverse (quantile) of the CDF.
Let \(p\) be a PMF on \(\mathrm{Fin}\, m\) with \(m \ge 1\), let \(x \lt 1\) in \(\mathbb {R}_{\ge 0}^\infty \), and let \(i \in \mathrm{Fin}\, m\). Then \(\mathrm{invCdf}(p, x) = i\) if and only if \(\mathrm{cdf}(p, i) \le x \lt \mathrm{cdf}(p, i+1)\).
Given a PMF \(p\) on \(\mathrm{Fin}\, m\) and a positive integer \(n\), the map \(\mathrm{uniformApprox}(p, n) : \mathrm{Fin}\, n \to \mathrm{Fin}\, m\) sends \(j \mapsto \mathrm{invCdf}(p, j/n)\), discretizing the unit interval into \(n\) equally spaced points and mapping each through the quantile function of \(p\).
For any \(n \in \mathbb {N}\) and real numbers \(a \le b\), the number of indices \(j \in \mathrm{Fin}\, n\) satisfying \(a \le j \lt b\) is at most \(b - a + 1\).
For any PMF \(p\) on \(\mathrm{Fin}\, m\), positive \(n\), and index \(i \in \mathrm{Fin}\, m\), the empirical frequency with which \(\mathrm{uniformApprox}(p, n)\) outputs \(i\) satisfies
For any finite probability space \(\Omega \) and any \(\delta \gt 0\), there exist \(n \in \mathbb {N}\) and a map \(\varphi : \mathrm{CoinTape}(n) \to \Omega \) such that for every set \(S \subseteq \Omega \),
Let \(\alpha \) be a finite type, \(p, q : \alpha \to \mathbb {R}\), and \(g : \alpha \to \mathbb {R}\) with \(0 \le g(a) \le 1\) for all \(a\). If \(\sum _{a \in T} p(a) \le \sum _{a \in T} q(a) + \delta \) for every finite set \(T\), then \(\sum _a p(a)\, g(a) \le \sum _a q(a)\, g(a) + \delta \).
For any two finite probability spaces \(\Omega _X\) and \(\Omega _Y\) and any \(\delta \gt 0\), there exist \(n_X, n_Y \in \mathbb {N}\) and maps \(\varphi _X : \mathrm{CoinTape}(n_X) \to \Omega _X\), \(\varphi _Y : \mathrm{CoinTape}(n_Y) \to \Omega _Y\) such that for every set \(S \subseteq \Omega _X \times \Omega _Y\),
Given a finite-message private-coin protocol \(p\) over finite probability spaces \(\Omega _X\) and \(\Omega _Y\), and a tolerance \(\delta \gt 0\), \(\mathrm{toCoinTape}(p, \delta )\) produces \(n_X\), \(n_Y\), and a new finite-message protocol over \(\mathrm{CoinTape}(n_X) \times \mathrm{CoinTape}(n_Y)\) obtained by precomposing \(p\) with the inverse-CDF approximating maps \(\varphi _X\) and \(\varphi _Y\).
The coin-tape conversion \(\mathrm{toCoinTape}(p, \delta , h_\delta )\) produces a protocol of the same communication complexity as \(p\), i.e. \(\mathrm{toCoinTape}(p, \delta , h_\delta )\mathtt{.snd.snd.complexity} = p\mathtt{.complexity}\).
If a protocol \(p\) approximately satisfies a predicate \(Q\) with error at most \(\varepsilon \), then the coin-tape conversion \(\mathrm{toCoinTape}(p, \delta , h_\delta )\) approximately satisfies \(Q\) with error at most \(\varepsilon + \delta \).