Let \(p\) be a private-coin finite-message communication protocol with input types \(X\) and \(Y\), private-randomness types \(\Omega _X\) and \(\Omega _Y\), and output type \(\alpha \), and let \(g \colon \alpha \to \beta \). Write \(\mathrm{map}(g, p)\) for the protocol that runs \(p\) and then applies \(g\) to the result, and let executing a protocol on inputs \(x, y\) with private coins \(\omega _x, \omega _y\) denote running it on the paired inputs \((\omega _x, x)\) and \((\omega _y, y)\). Then for all \(x \in X\), \(y \in Y\), \(\omega _x \in \Omega _X\), and \(\omega _y \in \Omega _Y\),

Let \(p\) be a private-coin finite-message protocol with input types \(X\), \(Y\), private-randomness types \(\Omega _X\), \(\Omega _Y\), and output type \(\alpha \), and let \(g \colon \alpha \to \beta \) be any function. Then the protocol obtained by running \(p\) and applying \(g\) to its output has the same communication complexity as \(p\), i.e. \(\mathrm{complexity}(\mathrm{map}\, g\, p) = \mathrm{complexity}(p)\).

Let \(p\) be a private-coin finite-message protocol with input types \(X\), \(Y\), private-coin types \(\Omega _X\), \(\Omega _Y\), and output type \(\alpha \), and let \(q\) assign to each value \(a \in \alpha \) a private-coin finite-message protocol \(q(a)\) over input types \(X\), \(Y\) and private-coin types \(\Omega _X\), \(\Omega _Y\) with output type \(\beta \). Then for all inputs \(x \in X\), \(y \in Y\) and private coins \(\omega _x \in \Omega _X\), \(\omega _y \in \Omega _Y\),

where \(a \in \alpha \) is the output of executing \(p\) on inputs \(x, y\) with coins \(\omega _x, \omega _y\). That is, running the sequential composition of \(p\) and \(q\) on inputs \(x, y\) with private coins \(\omega _x, \omega _y\) gives the value obtained by first running \(p\) on \(x, y\) with coins \(\omega _x, \omega _y\) to produce an output \(a\), and then running \(q(a)\) on \(x, y\) with coins \(\omega _x, \omega _y\).

Let \(p\) be a private-coin finite-message protocol over input types \(X\), \(Y\) with private-randomness types \(\Omega _X\), \(\Omega _Y\) and output type \(\alpha \), and let \(hX : \Omega _X' \to \Omega _X\) and \(hY : \Omega _Y' \to \Omega _Y\) be functions reindexing the two randomness spaces. Then for all inputs \(x : X\), \(y : Y\) and all coins \(\omega _x : \Omega _X'\), \(\omega _y : \Omega _Y'\), executing the reindexed protocol on \(x, y\) with coins \(\omega _x, \omega _y\) yields the same output as executing \(p\) itself on \(x, y\) with the pushed-forward coins \(hX(\omega _x)\) and \(hY(\omega _y)\).

Let \(p\) be a private-coin finite-message protocol over input types \(X\), \(Y\) with private-randomness types \(\Omega _X\), \(\Omega _Y\) and output type \(\alpha \), and let \(hX : \Omega _X' \to \Omega _X\) and \(hY : \Omega _Y' \to \Omega _Y\) be arbitrary maps of randomness spaces. Reindexing the randomness of \(p\) through \(hX\) and \(hY\) — that is, forming the protocol over \(\Omega _X'\), \(\Omega _Y'\) that maps its coins through \(hX\) and \(hY\) before feeding them to \(p\) — yields a protocol with the same worst-case communication complexity as \(p\).

Let \(p_1\) and \(p_2\) be private-coin finite-message protocols over the same input types \(X\) and \(Y\), with output types \(\alpha _1\) and \(\alpha _2\) and private-randomness types \((\Omega _{X_1}, \Omega _{Y_1})\) and \((\Omega _{X_2}, \Omega _{Y_2})\) respectively. Then for all inputs \(x : X\) and \(y : Y\), and all paired private coins \(\omega _x = (\omega _{x,1}, \omega _{x,2}) \in \Omega _{X_1} \times \Omega _{X_2}\) and \(\omega _y = (\omega _{y,1}, \omega _{y,2}) \in \Omega _{Y_1} \times \Omega _{Y_2}\), executing the product protocol of \(p_1\) and \(p_2\) yields the pair

where each component is the output of the corresponding factor run on the same inputs with its own share of the private randomness.

Let \(p_1\) and \(p_2\) be private-coin finite-message protocols, both over the same input types \(X\) and \(Y\), with private-randomness types \((\Omega _{X_1}, \Omega _{Y_1})\) and \((\Omega _{X_2}, \Omega _{Y_2})\) and output types \(\alpha _1\) and \(\alpha _2\) respectively. Their product, the protocol on inputs \(X\) and \(Y\) that runs \(p_1\) and \(p_2\) in parallel using independent randomness drawn from \(\Omega _{X_1} \times \Omega _{X_2}\) and \(\Omega _{Y_1} \times \Omega _{Y_2}\) and returns the pair of their outputs, has worst-case communication cost (in bits) equal to the sum of the individual costs:

Let \(k\) be a natural number and, for each \(i \in \mathrm{Fin}\, k\), let \(p_i\) be a private-coin finite-message protocol with private-randomness types \(\Omega _{X,i}\) for Alice and \(\Omega _{Y,i}\) for Bob, common public input types \(X\) and \(Y\), and output type \(\alpha _i\). Fix public inputs \(x \in X\) and \(y \in Y\), together with coin vectors \(\omega _x \in \prod _{i} \Omega _{X,i}\) and \(\omega _y \in \prod _{i} \Omega _{Y,i}\). Then executing the product protocol on these data agrees componentwise with executing each factor on its own coordinate of the randomness:

Let \(k\) be a natural number and let \(p_0, \dots , p_{k-1}\) be a family of private-coin finite-message protocols indexed by \(i \in \mathrm{Fin}\, k\), where \(p_i\) has private-randomness types \(\Omega _{X,i}\), \(\Omega _{Y,i}\), shared input types \(X\), \(Y\), and output type \(\alpha _i\). Then the communication complexity of their \(k\)-fold product protocol equals the sum of the individual communication complexities,

Let \(p\) be a private-coin finite-message protocol over inputs \(X\), \(Y\) with private randomness types \(\Omega _X\), \(\Omega _Y\) and output type \(\alpha \), and let \(q\) assign to each output \(a\in \alpha \) a private-coin finite-message protocol \(q(a)\) over the same inputs \(X\), \(Y\) with fresh randomness types \(\Omega _X'\), \(\Omega _Y'\) and output type \(\beta \). Then for all inputs \(x\in X\), \(y\in Y\) and all coin pairs \(\omega _x=(\omega _x^1,\omega _x^2)\in \Omega _X\times \Omega _X'\) and \(\omega _y=(\omega _y^1,\omega _y^2)\in \Omega _Y\times \Omega _Y'\), executing the fresh-randomness bind of \(p\) and \(q\) agrees with running \(p\) on the first coordinates of the coins to obtain an output \(a\) and then running \(q(a)\) on the second coordinates:

Let \(p\) be a private-coin finite-message protocol over inputs \(X\), \(Y\) with private randomness \((\Omega _X, \Omega _Y)\) and output type \(\alpha \), and let \(q\) assign to each output \(a \in \alpha \) a private-coin finite-message protocol \(q\, a\) over \(X\), \(Y\) with fresh randomness \((\Omega _X', \Omega _Y')\) and output type \(\beta \). Suppose there is a natural number \(c\) with \(\mathrm{complexity}(q\, a) = c\) for every \(a \in \alpha \). Then the protocol obtained by running \(p\) and then \(q\, a\) with independent randomness satisfies

Let \(X\), \(Y\) be input types and \(\Omega _X\), \(\Omega _Y\) private-randomness types. Let \(p_1\) be a private-coin finite-message protocol over these types with output type \(\alpha _1\), and let \(p_2\) be a deterministic finite-message protocol over \(X\), \(Y\) with output type \(\alpha _2\). Then for all inputs \(x : X\), \(y : Y\) and all private coins \(\omega _x : \Omega _X\), \(\omega _y : \Omega _Y\), executing the product protocol of \(p_1\) and \(p_2\) on \(x\), \(y\) with coins \(\omega _x\), \(\omega _y\) yields the pair whose first component is the output of \(p_1\) executed on \(x\), \(y\) with coins \(\omega _x\), \(\omega _y\) and whose second component is the output of the deterministic protocol \(p_2\) run on \(x\), \(y\).

Fix input types \(X\), \(Y\), a private-randomness type \(\Omega _X\) for Alice and \(\Omega _Y\) for Bob, and output types \(\alpha _1\), \(\alpha _2\). Let \(p_1\) be a private-coin finite-message protocol producing an output in \(\alpha _1\), and let \(p_2\) be a deterministic finite-message protocol over \(X\), \(Y\) producing an output in \(\alpha _2\). Form their product, the private-coin protocol that runs \(p_1\) and then \(p_2\) on the same inputs (with \(p_2\) using no private randomness) and reports the pair of their outputs in \(\alpha _1 \times \alpha _2\). Then the worst-case communication cost of this product equals the sum of the individual costs, that is, the complexity of the product is the complexity of \(p_1\) plus the complexity of \(p_2\).