Let \(f : X \to Y \to \alpha \) be a function of Alice’s input and Bob’s input, let \(\varepsilon \in \mathbb {R}\) be an error parameter, and let \(m \in \mathbb {N}\). Then the \(\varepsilon \)-error public-coin communication complexity satisfies \(\mathrm{R}^{\mathrm{pub}}_\varepsilon (f) \le m\) if and only if there exist a length \(n \in \mathbb {N}\) and a public-coin protocol \(p\) over the coin tape \(\mathrm{CoinTape}(n)\) such that \(p\) \(\varepsilon \)-computes \(f\) and the worst-case bit complexity 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}\). Write \(\mathrm{R}^{\mathrm{pub}}_\varepsilon (f)\) for the \(\varepsilon \)-error public-coin randomized communication complexity of \(f\), namely the infimum in \(\mathbb {N}\cup \{ \infty \} \) of the worst-case bit complexity over all public-coin protocols that compute \(f\) with error at most \(\varepsilon \) on every input. Then \(m \le \mathrm{R}^{\mathrm{pub}}_\varepsilon (f)\) if and only if, for every \(n \in \mathbb {N}\) and every public-coin protocol \(p\) using a coin tape of length \(n\), whenever \(p\) \(\varepsilon \)-computes \(f\) its communication complexity satisfies \(m \le \mathrm{complexity}(p)\).

Fix an output type \(\alpha \), a function \(f : X \to Y \to \alpha \), an error tolerance \(\varepsilon \in \mathbb {R}\), and a natural number \(m\). Then the \(\varepsilon \)-error public-coin randomized communication complexity of \(f\) satisfies \(\mathrm{R}^{\mathrm{pub}}_\varepsilon (f) \le m\) if and only if there exist a coin-tape length \(n \in \mathbb {N}\) and a public-coin finite-message protocol \(p\) over the shared randomness \(\mathrm{CoinTape}(n)\) such that \(p\) \(\varepsilon \)-computes \(f\) — that is, for every input pair \((x,y)\) the probability over the coin tape \(\omega \) that \(p\) outputs a value other than \(f(x,y)\) is at most \(\varepsilon \) — and the communication complexity of \(p\) is at most \(m\).

Let \(f : X \to Y \to \alpha \) be a function of two arguments, and let \(\varepsilon , \varepsilon ' \in \mathbb {R}\) be error parameters with \(\varepsilon ' \le \varepsilon \). Then the \(\varepsilon \)-error public-coin randomized communication complexity of \(f\) is at most its \(\varepsilon '\)-error public-coin randomized communication complexity: \(\mathrm{R}^{\mathrm{pub}}_\varepsilon (f) \le \mathrm{R}^{\mathrm{pub}}_{\varepsilon '}(f)\), this inequality holding in \(\mathbb {N}_\infty \). That is, permitting a larger error tolerance can only decrease the worst-case number of bits that must be exchanged.

Let \(X\), \(Y\), and \(\alpha \) be types, let \(\Omega \) be a finite probability space, and let \(f : X \to Y \to \alpha \). Fix real numbers \(\varepsilon ' \lt \varepsilon \), and suppose \(p\) is a public-coin finite-message protocol with shared randomness \(\Omega \) and private inputs in \(X\) and \(Y\) that \(\varepsilon '\)-computes \(f\), meaning that for every input pair \((x,y)\) the probability over \(\omega \in \Omega \) that the protocol’s output differs from \(f(x,y)\) is at most \(\varepsilon '\). Then the \(\varepsilon \)-error public-coin randomized communication complexity of \(f\) satisfies

where \(\mathrm{complexity}(p)\) is the worst-case bit cost of \(p\) (a \(\beta \)-valued message costing \(\lceil \log _2 \left\lvert \beta \right\rvert \rceil \) bits) and the inequality holds in \(\mathbb {N}\cup \{ \infty \} \).