Let \(f : X \to Y \to \alpha \) be a function, let \(\varepsilon \in \mathbb {R}\) be an error bound, and let \(n \in \mathbb {N}\). Then the \(\varepsilon \)-error private-coin randomized communication complexity of \(f\) is at most \(n\) if and only if there exist coin-tape lengths \(n_X, n_Y \in \mathbb {N}\) and a private-coin protocol \(p\) with Alice’s randomness space \(\{ 0,1\} ^{n_X}\) and Bob’s randomness space \(\{ 0,1\} ^{n_Y}\), inputs in \(X\) and \(Y\), and outputs in \(\alpha \), such that \(p\) computes \(f\) with error at most \(\varepsilon \) on every input and the communication complexity of \(p\) is at most \(n\).

Let \(f : X \to Y \to \alpha \) be a function, let \(\varepsilon \in \mathbb {R}\), and let \(R_\varepsilon (f) \in \mathbb {N}\cup \{ \infty \} \) denote its \(\varepsilon \)-error private-coin randomized communication complexity, namely the least worst-case number of bits exchanged by any private-coin protocol that computes \(f\) with error probability at most \(\varepsilon \) on every input. Then for every \(n \in \mathbb {N}\), the inequality \(n \le R_\varepsilon (f)\) holds (in the extended natural numbers) if and only if every private-coin protocol \(p\) — over coin tapes \(\{ 0,1\} ^{n_X}\) for Alice and \(\{ 0,1\} ^{n_Y}\) for Bob, for arbitrary lengths \(n_X, n_Y \in \mathbb {N}\) — that \(\varepsilon \)-computes \(f\) has communication complexity at least \(n\).

Let \(f : X \to Y \to \alpha \) be a function, let \(\varepsilon \in \mathbb {R}\) be an error bound, and let \(n \in \mathbb {N}\). Then the \(\varepsilon \)-error private-coin randomized communication complexity satisfies \(R_\varepsilon (f) \le n\) if and only if there exist coin-tape lengths \(n_X, n_Y \in \mathbb {N}\) and a private-coin finite-message protocol \(p\) with randomness spaces \(\{ 0,1\} ^{n_X}\) and \(\{ 0,1\} ^{n_Y}\) (over input types \(X\), \(Y\) and output type \(\alpha \)) such that \(p\) computes \(f\) with error at most \(\varepsilon \) on every input pair and has worst-case communication cost at most \(n\). Thus the private-coin complexity, defined via binary-message protocols, is unchanged when one instead allows protocols whose players may send elements of arbitrary finite nonempty message alphabets, each \(\beta \)-valued message being charged \(\lceil \log _2 \left\lvert \beta \right\rvert \rceil \) bits.

Let \(f : X \to Y \to \alpha \) be a function of two arguments, and let \(R_\varepsilon (f)\) denote its \(\varepsilon \)-error private-coin randomized communication complexity — the least worst-case number of bits exchanged by any private-coin protocol computing \(f\) with probability of error at most \(\varepsilon \) on every input, taken as an extended natural number. Then for any two error bounds \(\varepsilon ', \varepsilon \in \mathbb {R}\) with \(\varepsilon ' \le \varepsilon \), we have \(R_\varepsilon (f) \le R_{\varepsilon '}(f)\); that is, allowing a larger error can only decrease or preserve the required communication.

Let \(X\), \(Y\), and \(\alpha \) be types, let \(f : X \to Y \to \alpha \) be the function to be computed, and let \(\Omega _X\) and \(\Omega _Y\) be finite probability spaces serving as the two players’ private randomness. Fix real numbers \(\varepsilon '\) and \(\varepsilon \) with \(\varepsilon ' \lt \varepsilon \), and let \(p\) be a finite-message private-coin protocol with randomness spaces \(\Omega _X\) and \(\Omega _Y\), input types \(X\) and \(Y\), and output type \(\alpha \), and suppose that \(p\) computes \(f\) with error at most \(\varepsilon '\), i.e. for every input pair \((x,y)\) the probability that \(p\) returns a value other than \(f(x,y)\) is at most \(\varepsilon '\). Then the \(\varepsilon \)-error private-coin randomized communication complexity of \(f\) satisfies \(R_\varepsilon (f) \le \mathrm{complexity}(p)\), where the right-hand side is the worst-case number of bits exchanged by \(p\).