Let \(p\) be a public-coin finite-message protocol over shared-randomness space \(\Omega \), private input sets \(X\) and \(Y\), and output type \(\alpha \), and let \(g\colon \alpha \to \beta \) be any function. Write \(\mathrm{map}(g,p)\) for the protocol with the same communication structure as \(p\) that applies \(g\) to whatever value \(p\) outputs, and write \(\mathrm{rrun}(q,x,y,\omega )\) for the result of executing a protocol \(q\) on private inputs \(x\) and \(y\) with shared randomness \(\omega \). Then for all \(x\in X\), \(y\in Y\), and \(\omega \in \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 \(g : \alpha \to \beta \) be any function. Then the protocol \(p.\mathrm{map}\, g\), which runs \(p\) and applies \(g\) to its output, has the same communication complexity as \(p\):

Let \(p\) be a public-coin finite-message protocol with shared-randomness space \(\Omega \), private input sets \(X\) and \(Y\), and output type \(\alpha \), and let \(q\) be a family of such protocols indexed by \(\alpha \) with output type \(\beta \), all sharing the same randomness space \(\Omega \). Then for every private input \(x \in X\), every private input \(y \in Y\), and every shared random string \(\omega \in \Omega \), the randomized execution of the sequential composition \(p.\mathrm{bind}\, q\) agrees with first executing \(p\) and then executing the selected continuation:

Let \(h : \Omega ' \to \Omega \) be a map between shared-randomness spaces, and let \(p\) be a public-coin finite-message protocol over randomness space \(\Omega \), private input sets \(X\) and \(Y\), and output type \(\alpha \). Form the reindexed protocol over \(\Omega '\) that pre-composes the shared randomness with \(h\) before running \(p\). Then for all private inputs \(x \in X\) and \(y \in Y\) and all shared randomness \(\omega \in \Omega '\), executing the reindexed protocol on inputs \(x, y\) with randomness \(\omega \) produces the same output as executing \(p\) on inputs \(x, y\) with randomness \(h(\omega )\).

Let \(p\) be a public-coin finite-message protocol with shared-randomness space \(\Omega \), private inputs \(X\) and \(Y\), and outputs in \(\alpha \), and let \(h : \Omega ' \to \Omega \) be any map. Form the protocol over the new randomness space \(\Omega '\) by replacing each player’s effective input \(\Omega \times X\) or \(\Omega \times Y\) with \(\Omega ' \times X\) or \(\Omega ' \times Y\) and precomposing every message function with \(h\) on the randomness coordinate (leaving the private inputs untouched). Then this reindexed protocol has exactly the same worst-case communication complexity as \(p\).

Let \(p_1\) be a public-coin finite-message protocol with shared-randomness space \(\Omega _1\) and output type \(\alpha _1\), and let \(p_2\) be one with shared-randomness space \(\Omega _2\) and output type \(\alpha _2\), both over the same private input sets \(X\) (Alice’s) and \(Y\) (Bob’s). Then for every pair of inputs \(x \in X\), \(y \in Y\) and every joint random string \(\omega = (\omega _1, \omega _2) \in \Omega _1 \times \Omega _2\), the randomized execution of the product protocol \(\mathrm{prod}(p_1, p_2)\) decomposes into the executions of its factors:

that is, each component is obtained by running the corresponding factor on the same inputs \(x\), \(y\) with the matching component of the shared randomness.

Let \(p_1\) and \(p_2\) be public-coin finite-message protocols over the common private input sets \(X\) and \(Y\), with shared-randomness spaces \(\Omega _1\) and \(\Omega _2\) and output types \(\alpha _1\) and \(\alpha _2\) respectively. Then the communication complexity of their product protocol \(\mathrm{prod}\; p_1\; p_2\), which runs \(p_1\) and \(p_2\) independently on the same inputs, equals the sum of the individual complexities:

Fix \(k \in \mathbb {N}\), shared private-input sets \(X\) and \(Y\), and, for each index \(i \in \mathrm{Fin}\, k\), a randomness space \(\Omega _i\) and an output type \(\alpha _i\). Let \(p = (p_i)_{i}\) be a family of public-coin finite-message protocols, where \(p_i\) has randomness space \(\Omega _i\), private inputs from \(X\) and \(Y\), and outputs in \(\alpha _i\), and let \(\mathrm{pi}\, p\) be their \(k\)-fold product, a public-coin protocol with randomness space \(\prod _i \Omega _i\) and output type \(\prod _i \alpha _i\). Then for all inputs \(x \in X\), \(y \in Y\) and every randomness tuple \(\omega = (\omega _i)_i \in \prod _i \Omega _i\), the randomized execution of the product on \((x, y, \omega )\) is the tuple of the individual executions:

Let \(k\) be a natural number, and for each index \(i \in \mathrm{Fin}\, k\) let \(p_i\) be a public-coin finite-message protocol with shared-randomness space \(\Omega _i\), common private input sets \(X\) and \(Y\), and output type \(\alpha _i\). Then the communication complexity of their \(k\)-fold product — the protocol \(\mathrm{pi}\, p\) over the combined randomness space \(\prod _i \Omega _i\) that runs each \(p_i\) on its own randomness component and returns the tuple of outputs — is the sum of the complexities of the factors:

Let \(p\) be a public-coin finite-message protocol over shared-randomness space \(\Omega \) with private inputs in \(X\), \(Y\) and outputs in \(\alpha \), and let \(q\) assign to each output \(a \in \alpha \) a public-coin finite-message protocol \(q(a)\) over shared-randomness space \(\Omega '\) with the same private input sets and outputs in \(\beta \). Then for all private inputs \(x \in X\) and \(y \in Y\) and every randomness pair \(\omega = (\omega _1, \omega _2) \in \Omega \times \Omega '\), the randomized execution of the fresh-randomness bind \(\mathrm{rbind}(p, q)\) satisfies

That is, running the bound protocol with randomness \(\omega \) is the same as first running \(p\) on \(x, y\) with the randomness \(\omega _1\) to obtain an output, and then running the protocol \(q\) assigns to that output on \(x, y\) with the independent randomness \(\omega _2\).

Let \(p\) be a public-coin finite-message protocol over shared randomness \(\Omega \), private inputs \(X\) and \(Y\), and outputs \(\alpha \), and let \(q\) assign to each output value \(a \in \alpha \) a public-coin finite-message protocol \(q(a)\) over fresh, independent shared randomness \(\Omega '\), with the same private inputs \(X\) and \(Y\) and outputs in \(\beta \). If there is a constant \(c \in \mathbb {N}\) such that every continuation \(q(a)\) has communication complexity exactly \(c\), then the protocol \(\mathrm{rbind}(p, q)\) — which runs \(p\) on the \(\Omega \)-component of the randomness and then runs the selected \(q(a)\) on the independent \(\Omega '\)-component — has communication complexity \(\mathrm{complexity}(p) + c\).

Let \(p_1\) be a public-coin finite-message protocol over shared-randomness space \(\Omega \), private input sets \(X\) and \(Y\), and output type \(\alpha _1\), and let \(p_2\) be a deterministic finite-message protocol over \(X\) and \(Y\) with output type \(\alpha _2\). Write \(p_1 \times p_2\) for their product: the public-coin protocol with output type \(\alpha _1 \times \alpha _2\) that runs both on the same private inputs and the same shared randomness and pairs their outputs. Denote by \(p_1(x, y; \omega )\) the output of executing \(p_1\) on private inputs \(x\) and \(y\) with shared randomness \(\omega \), and by \(p_2(x, y)\) the output of executing the deterministic protocol \(p_2\) on \(x\) and \(y\). Then for every pair of private inputs \(x \in X\), \(y \in Y\) and every value \(\omega \in \Omega \) of the shared randomness,

Let \(\Omega \) be a shared-randomness space and let \(X\), \(Y\) be private input sets. Let \(p_1\) be a public-coin finite-message protocol over \(\Omega \), \(X\), \(Y\) with output type \(\alpha _1\), and let \(p_2\) be a deterministic finite-message protocol over \(X\), \(Y\) with output type \(\alpha _2\). Form their product: the public-coin protocol over \(\Omega \), \(X\), \(Y\) with output type \(\alpha _1 \times \alpha _2\) that runs both \(p_1\) and \(p_2\) on the same inputs, sharing the randomness \(\Omega \), and returns the pair of their outputs. Then the worst-case communication complexity of this product protocol equals the sum of the complexities of \(p_1\) and \(p_2\).