For any inputs \(x : X\) and \(y : Y\), running the deterministic protocol \((p.\mathrm{toDeterministic}\, \omega )\) on \((x, y)\) yields the same output as running the randomised protocol \(p\) on \((x, y, \omega )\), i.e. \((p.\mathrm{toDeterministic}\, \omega ).\mathrm{run}\, x\, y = p.\mathrm{rrun}\, x\, y\, \omega \).

Fixing the shared randomness does not change the communication complexity: \((p.\mathrm{toDeterministic}\, \omega ).\mathrm{complexity} = p.\mathrm{complexity}\) for every \(\omega : \Omega \).

For any inputs \(x : X\), \(y : Y\) and any coin draws \(\omega _X : \Omega _X\), \(\omega _Y : \Omega _Y\), the randomised run of \(p.\mathrm{toPrivateCoin}\) equals the deterministic run of \(p\): \(\mathrm{rrun}(p.\mathrm{toPrivateCoin})\, x\, y\, \omega _X\, \omega _Y = p.\mathrm{run}\, x\, y\).

Embedding a deterministic finite-message protocol into the private-coin model preserves its complexity: \((p.\mathrm{toPrivateCoin}).\mathrm{complexity} = p.\mathrm{complexity}\).

For any inputs \(x : X\) and \(y : Y\), the deterministic run of \(p.\mathrm{toDeterministic}\, \omega \) equals the randomised run at \(\omega \): \((p.\mathrm{toDeterministic}\, \omega ).\mathrm{run}\, x\, y = p.\mathrm{rrun}\, x\, y\, \omega \).

Fixing the shared randomness of a public-coin finite-message protocol does not change its complexity: \((p.\mathrm{toDeterministic}\, \omega ).\mathrm{complexity} = p.\mathrm{complexity}\).

For any function \(f : X \to Y \to \alpha \) and any error parameter \(\varepsilon \ge 0\), the private-coin communication complexity satisfies

The inequality holds because every deterministic protocol can be viewed as a private-coin protocol with zero error by embedding it via toPrivateCoin.