Let \(p\) be a public-coin protocol over a randomness space \(\Omega \), with Alice’s private input in \(X\), Bob’s in \(Y\), and output in \(\alpha \), and fix a random outcome \(\omega \in \Omega \). For all private inputs \(x \in X\) and \(y \in Y\), executing the deterministic protocol obtained from \(p\) by fixing the shared randomness to \(\omega \) on the pair \((x, y)\) returns the same output in \(\alpha \) as the randomised execution of \(p\) on \(x\) and \(y\) with shared random string \(\omega \).

Let \(p\) be a public-coin communication protocol over a shared randomness space \(\Omega \), with Alice’s private input in \(X\), Bob’s in \(Y\), and output in \(\alpha \), and let \(\omega \in \Omega \) be any outcome of the shared randomness. Then the communication complexity of the deterministic protocol obtained from \(p\) by fixing the shared randomness to \(\omega \) equals the communication complexity of \(p\) itself.

Let \(p\) be a deterministic finite-message protocol over input types \(X\) and \(Y\) with output type \(\alpha \), and fix arbitrary private-coin spaces \(\Omega _X\) and \(\Omega _Y\). Form from \(p\) the private-coin protocol over \(\Omega _X\), \(\Omega _Y\) that runs \(p\) on the underlying inputs while discarding both players’ coins. Then for all inputs \(x \in X\), \(y \in Y\) and all coin draws \(\omega _x \in \Omega _X\), \(\omega _y \in \Omega _Y\), executing this private-coin protocol on \(x\), \(y\) with the coins \(\omega _x\), \(\omega _y\) returns exactly the value that the deterministic execution of \(p\) on \(x\), \(y\) produces, regardless of the coins.

Let \(p\) be a deterministic finite-message protocol over input types \(X\), \(Y\) and output type \(\alpha \), and let \(\Omega _X\), \(\Omega _Y\) be arbitrary types to serve as private-randomness spaces. Form the private-coin finite-message protocol over \(\Omega _X\), \(\Omega _Y\) obtained from \(p\) by having each player ignore their private coin, so that Alice’s message function \(f : X \to \beta \) is replaced by \((\omega , x) \mapsto f(x)\) and Bob’s by \((\omega , y) \mapsto f(y)\), with the protocol tree otherwise unchanged. Then this private-coin protocol has the same communication complexity as \(p\).

Let \(p\) be a public-coin finite-message protocol over a shared-randomness space \(\Omega \), private input sets \(X\) and \(Y\), and output type \(\alpha \). Fix a randomness sample \(\omega \in \Omega \) and private inputs \(x \in X\) and \(y \in Y\), and let \(p_\omega \) denote the deterministic finite-message protocol obtained from \(p\) by substituting \(\omega \) for the shared randomness. Then executing \(p_\omega \) on \(x\) and \(y\) yields the same output as the randomized execution of \(p\) on \(x\) and \(y\) with shared randomness \(\omega \):

Let \(p\) be a public-coin finite-message protocol over a shared-randomness space \(\Omega \), private input sets \(X\) and \(Y\), and output type \(\alpha \), and let \(\omega \in \Omega \) be any fixed randomness sample. Then the deterministic finite-message protocol obtained by substituting \(\omega \) for the shared randomness has the same communication complexity as \(p\) itself.

Let \(f : X \times Y \to \alpha \) be a function of two arguments, and let \(\varepsilon \ge 0\) be an error parameter. Then the \(\varepsilon \)-error private-coin randomized communication complexity of \(f\) is at most its deterministic communication complexity:

as an inequality of extended natural numbers.