64 Communication Complexity — Public Coin Approximation
64.1 Overview
This module provides the bridge between public-coin protocols over arbitrary finite probability spaces and those using the canonical CoinTape randomness source. The key result is that any finite-message public-coin protocol can be approximated by a CommunicationComplexity.CoinTape-based protocol of equal complexity, with the approximation error degrading by at most the chosen slack \(\delta \gt 0\).
64.2 Declarations
Given a public-coin finite-message protocol \(p\) over an arbitrary finite probability space \(\Omega \) and a slack \(\delta \gt 0\), this definition produces a natural number \(n\) together with a finite-message protocol over \(\mathrm{CoinTape}(n)\) that approximates \(p\). The construction works by pulling back \(p\) along a measure-approximating map \(\varphi : \mathrm{CoinTape}(n) \to \Omega \) provided by CommunicationComplexity.Internal.single_coin_approx.
Let \(\Omega \) be a finite probability space, and let \(p\) be a public-coin finite-message protocol over shared randomness \(\Omega \) with input sets \(X\), \(Y\) and output type \(\alpha \). For every real number \(\delta \gt 0\), the coin-tape conversion of \(p\) at slack \(\delta \) yields a length \(n\) and a finite-message protocol over \(\mathrm{CoinTape}(n)\) whose communication complexity equals the communication complexity of \(p\).
Let \(p\) be a public-coin finite-message protocol over a finite probability space \(\Omega \), with private input sets \(X\) and \(Y\) and outputs in \(\alpha \); let \(Q : X \to Y \to \alpha \to \mathrm{Prop}\) be a predicate; and let \(\varepsilon \) and \(\delta \) be real numbers with \(\delta \gt 0\). If \(p\) approximately satisfies \(Q\) with error at most \(\varepsilon \), then the coin-tape protocol obtained by converting \(p\) with slack \(\delta \) approximately satisfies \(Q\) with error at most \(\varepsilon + \delta \).