Fix a depth \(d \in \mathbb {N}\), a family of binary query functions \(\mathrm{query}_i : X \to \mathrm{Bool}\) for \(i \in \mathrm{Fin}\, d\), and a family of deterministic protocols \(Q(b)\) indexed by bit patterns \(b : \mathrm{Fin}\, d \to \mathrm{Bool}\). Then for every pair of inputs \(x : X\) and \(y : Y\), the protocol that first has Alice read the \(d\) query bits in sequence and then runs \(Q\) on the collected pattern evaluates on \((x,y)\) to the same value as the single protocol \(Q\bigl(i \mapsto \mathrm{query}_i(x)\bigr)\) evaluated on \((x,y)\).

Fix a natural number \(d\), together with binary query functions \(\mathrm{query}_0,\dots ,\mathrm{query}_{d-1} : X \to \mathrm{Bool}\) and a family of deterministic protocols \(Q(\mathrm{bits})\) indexed by the bit patterns \(\mathrm{bits} : \mathrm{Fin}\, d \to \mathrm{Bool}\). Form the protocol that has Alice read the bits \(\mathrm{query}_0(x),\dots ,\mathrm{query}_{d-1}(x)\) in sequence and then run \(Q\) on the collected pattern. Its communication complexity is

the maximum being taken over all \(2^d\) length-\(d\) bit patterns.

Let \(X\), \(Y\), and \(\alpha \) be types, let \(\beta \) be a finite nonempty type, let \(f : X \to \beta \) be a function, and let \(Q : \beta \to \mathrm{Protocol}\, X\, Y\, \alpha \) assign to each value \(b \in \beta \) a deterministic two-party communication protocol. Then there exists a deterministic protocol \(R\) over the same input types such that, on every pair of inputs \(x : X\) and \(y : Y\), running \(R\) yields the same output as running the protocol \(Q(f(x))\), and the communication complexity of \(R\) equals

where \(\left\lvert \beta \right\rvert \) denotes the cardinality of \(\beta \).

Let \(X\), \(Y\), and \(\alpha \) be types, and let \(p\) be a finite-message two-party protocol over inputs \(X\) (Alice) and \(Y\) (Bob) with output type \(\alpha \), in which each message ranges over an arbitrary finite nonempty type and a \(\beta \)-valued message is charged \(\lceil \log _2 |\beta | \rceil \) bits. Then there exists a binary deterministic protocol \(P\) over the same input types \(X\), \(Y\) and output type \(\alpha \) — one in which every message is a single bit — that computes the same function, i.e. \(P\) and \(p\) return the same output on every pair of inputs, and has exactly the same communication complexity as \(p\).

Let \(p\) be a finite-message deterministic two-party protocol over input types \(X\) and \(Y\) with output type \(\alpha \), and let \(q\) be the binary protocol obtained by converting \(p\) (encoding each message drawn from a finite nonempty type \(\beta \) as \(\lceil \log _2 \left\lvert \beta \right\rvert \rceil \) bits). Then \(q\) computes the same function as \(p\): for every pair of inputs \(x \in X\) and \(y \in Y\), running \(q\) on \((x, y)\) returns the same value in \(\alpha \) as running \(p\) on \((x, y)\).

Let \(p\) be a finite-message deterministic two-party communication protocol over input types \(X\) (Alice) and \(Y\) (Bob) with outputs in \(\alpha \), in which each message is an element of an arbitrary finite nonempty type. Its conversion into a binary protocol, obtained by encoding every \(\beta \)-valued message as \(\lceil \log _2 \left\lvert \beta \right\rvert \rceil \) bits, has communication complexity equal to that of \(p\).

Let \(X\) and \(Y\) be the input types of Alice and Bob, let \(\alpha \) be an output type, and let \(p\) be a deterministic binary two-party communication protocol producing values in \(\alpha \). Regard \(p\) as a finite-message protocol by treating each of its Boolean messages as an element of the two-element type. Then for all inputs \(x \in X\) and \(y \in Y\), executing this embedded finite-message protocol on \(x\) and \(y\) yields the same value in \(\alpha \) as executing \(p\) directly on \(x\) and \(y\).

Let \(p\) be a deterministic binary two-party communication protocol over input types \(X\) and \(Y\) with output type \(\alpha \), and let its embedding into the finite-message framework send each Boolean message as an element of \(\{ \mathtt{false},\mathtt{true}\} \). Then the communication complexity of the embedded finite-message protocol equals the communication complexity of \(p\).

Let \(X\) and \(Y\) be the input types of Alice and Bob and let \(\alpha \) be an output type. For every binary deterministic communication protocol \(p\) over \(X\), \(Y\), and \(\alpha \), there is a finite-message protocol \(P\) over the same input and output types that computes the same output on every pair of inputs — that is, \(\mathrm{run}(P) = \mathrm{run}(p)\) as functions of \(x \in X\) and \(y \in Y\) — and has the same communication complexity, \(\mathrm{complexity}(P) = \mathrm{complexity}(p)\).

Let \(p\) be a finite-message deterministic communication protocol over input types \(X\), \(Y\) with output type \(\alpha \), and let \(f_X : X' \to X\) and \(f_Y : Y' \to Y\) be maps into those input types. Then for every pair of inputs \(x' : X'\) and \(y' : Y'\), executing the pullback protocol \(p.\mathrm{comap}\, f_X\, f_Y\) on \((x', y')\) yields the same output as executing \(p\) on the transported inputs \((f_X(x'), f_Y(y'))\); that is,

Let \(p\) be a finite-message deterministic communication protocol over input types \(X\) and \(Y\) with output type \(\alpha \), and let \(f_X : X' \to X\) and \(f_Y : Y' \to Y\) be maps of input types. Then the pullback protocol obtained by precomposing every message function of \(p\) with \(f_X\) or \(f_Y\) (as appropriate) has the same communication complexity as \(p\).

The ceiling base-\(2\) logarithm of \(2\) equals \(1\): \(\lceil \log _2 2 \rceil = 1\), i.e. Nat.clog 2 2 = 1. This is a numeric fact used when comparing the complexity of a binary protocol with its finite-message reformulation.