Let \(p\) be a one-way public-coin protocol with shared-randomness type \(\Omega \), input types \(X\) and \(Y\), and output type \(\alpha \); let \(\omega \in \Omega \) be a coin outcome and \(x \in X\), \(y \in Y\) be inputs. Fixing the public coin at \(\omega \) turns \(p\) into a deterministic one-way protocol, and executing that deterministic protocol on inputs \(x\) and \(y\) yields the same output as running \(p\) on the joint inputs \((\omega , x)\) for Alice and \((\omega , y)\) for Bob. In both cases the output is Bob’s decoder applied to his input \((\omega , y)\) together with the message that Alice’s encoder assigns to \((\omega , x)\).

Let \(p\) be a one-way public-coin protocol over a shared randomness type \(\Omega \), with input types \(X\), \(Y\) and output type \(\alpha \), and let \(\omega \in \Omega \) be a fixed coin outcome. Then the deterministic one-way protocol obtained from \(p\) by substituting \(\omega \) for the public randomness has the same communication cost as \(p\); that is, both have cost \(\lceil \log _2 |M| \rceil \) bits, where \(M\) is the shared message codebook.

Let \(f : X \to Y \to \alpha \) be a function, let \(\varepsilon \in \mathbb {R}\), and let \(n \in \mathbb {N}\). Suppose there is a finite probability distribution \(\mu \) on \(X \times Y\) under which every deterministic one-way protocol \(p\) of communication cost at most \(n\) has distributional error strictly greater than \(\varepsilon \); that is, \(\Pr _{(x,y)\sim \mu }\bigl[\, p\text{ outputs a value}\neq f(x,y)\, \bigr] \gt \varepsilon \) for every such \(p\). Then the \(\varepsilon \)-error one-way public-coin communication complexity of \(f\) is strictly greater than \(n\).