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\).