69 Communication Complexity — Public Coin One Way
69.1 Overview
This module defines one-way public-coin protocols and their \(\varepsilon \)-error communication complexity. A public-coin protocol is modelled as a deterministic one-way protocol whose input spaces are augmented with a shared randomness type \(\Omega \); correctness is measured by the probability (over the shared randomness) that the protocol’s output disagrees with the target function.
69.2 Declarations
A one-way public-coin protocol over shared randomness type \(\Omega \) and input types \(X\), \(Y\) with output type \(\alpha \) is defined as a deterministic one-way protocol whose Alice-input is \(\Omega \times X\) and whose Bob-input is \(\Omega \times Y\). The shared randomness \(\omega \in \Omega \) is thus treated as a component of both players’ inputs.
Given a protocol \(p\), inputs \(x \in X\), \(y \in Y\), and a shared random string \(\omega \in \Omega \), the execution \(\mathrm{rrun}(p, x, y, \omega )\) runs \(p\) on the joint inputs \((\omega , x)\) for Alice and \((\omega , y)\) for Bob, returning the decoded output \(p.\mathrm{decode}(p.\mathrm{send}(\omega , x),\, (\omega , y))\).
A protocol \(p\) \(\varepsilon \)-computes a function \(f : X \to Y \to \alpha \) if for every input pair \((x, y)\) the measure of the set of shared strings on which \(p\) errs is at most \(\varepsilon \):
The \(\varepsilon \)-error one-way public-coin communication complexity of \(f : X \to Y \to \alpha \) is the infimum (in \(\mathbb {N}_\infty \)) of the one-way message cost \(p.\mathrm{cost}\) over all \(n \in \mathbb {N}\) and all protocols \(p\) over the coin-tape space \(\mathrm{CoinTape}(n)\) that \(\varepsilon \)-compute \(f\).
Fix a function \(f : X \to Y \to \alpha \), a real error bound \(\varepsilon \), and a natural number \(m\). Then the \(\varepsilon \)-error one-way public-coin communication complexity of \(f\) is at most \(m\) (as an element of \(\mathbb {N}_\infty \)) if and only if there exist a length \(n \in \mathbb {N}\) and a one-way public-coin protocol \(p\) over the coin-tape space \(\mathrm{CoinTape}(n)\) such that \(p\) \(\varepsilon \)-computes \(f\) and the bit cost of \(p\) is at most \(m\).
Let \(f : X \to Y \to \alpha \) be a function, let \(\varepsilon \in \mathbb {R}\), and let \(m \in \mathbb {N}\). Then \(m\) is a lower bound for the \(\varepsilon \)-error one-way public-coin communication complexity of \(f\), in the sense that \(m \le \mathrm{CC}(f,\varepsilon )\) as elements of \(\mathbb {N}_\infty \), if and only if every protocol \(p\) over a coin tape \(\mathrm{CoinTape}(n)\) of any length \(n \in \mathbb {N}\) that \(\varepsilon \)-computes \(f\) has bit cost at least \(m\).
Fix a function \(f : X \to Y \to \alpha \) and real error tolerances \(\varepsilon ', \varepsilon \) with \(\varepsilon ' \le \varepsilon \). Then the \(\varepsilon \)-error one-way public-coin communication complexity of \(f\) is at most its \(\varepsilon '\)-error one-way public-coin communication complexity, where each such complexity is the infimum (in \(\mathbb {N}\cup \{ \infty \} \)) of the bit cost over all coin-tape lengths \(n\) and all one-way public-coin protocols that compute \(f\) to the corresponding error tolerance. In other words, relaxing the permitted error can only decrease (or leave unchanged) the required communication.