A private-coin protocol with randomness spaces \(\Omega _X\) and \(\Omega _Y\), input spaces \(X\) and \(Y\), and output type \(\alpha \) is defined as a deterministic protocol \(\texttt{Deterministic.Protocol}\; (\Omega _X \times X)\; (\Omega _Y \times Y)\; \alpha \). Alice’s message function receives the pair \((\omega _x, x)\) and Bob’s receives \((\omega _y, y)\), so each player’s coin flip is invisible to the other.

The constant output node of a private-coin protocol that immediately returns the value \(a : \alpha \), without any further communication.

Given a function \(f : X \to \Omega _X \to \mathrm{Bool}\) and a continuation \(P : \mathrm{Bool} \to \mathrm{Protocol}\; \Omega _X\; \Omega _Y\; X\; Y\; \alpha \), constructs the protocol node at which Alice sends the bit \(f\, x\, \omega _x\) and execution continues with \(P(\text{bit})\).

Given a function \(f : Y \to \Omega _Y \to \mathrm{Bool}\) and a continuation \(P : \mathrm{Bool} \to \mathrm{Protocol}\; \Omega _X\; \Omega _Y\; X\; Y\; \alpha \), constructs the protocol node at which Bob sends the bit \(f\, y\, \omega _y\) and execution continues with \(P(\text{bit})\).

\(\texttt{rrun}\; p\; x\; y\; \omega _x\; \omega _y\) executes the private-coin protocol \(p\) on inputs \(x \in X\) and \(y \in Y\) with Alice’s private coin \(\omega _x \in \Omega _X\) and Bob’s private coin \(\omega _y \in \Omega _Y\), returning the output \(\alpha \). It is defined by \(p.\mathrm{run}\, (\omega _x, x)\, (\omega _y, y)\).

A private-coin protocol \(p\) \(\varepsilon \)-satisfies a predicate \(Q : X \to Y \to \alpha \to \mathrm{Prop}\) if for every input pair \((x, y)\),

where \(\mu \) is the product measure on \(\Omega _X \times \Omega _Y\).

A private-coin protocol \(p\) \(\varepsilon \)-computes a function \(f : X \to Y \to \alpha \) if for every input pair \((x, y)\),

This formalises the standard notion of bounded-error private-coin randomized communication complexity.