Let \(s\), \(t\), and \(u\) be deterministic two-party communication protocols over the same input types and output type. If \(s\) is a subprotocol of \(t\) and \(t\) is a subprotocol of \(u\), then \(s\) is a subprotocol of \(u\). In other words, the subprotocol relation is transitive.

Let \(p\) be a deterministic two-party communication protocol, and let \(n\) be a natural number with \(n \gt 1\). Write \(\ell (q)\) for the number of leaves of a protocol \(q\), and suppose that \(3\, \ell (p) \ge 2n\). Then there is a subprotocol \(s\) of \(p\) (a rooted subtree of \(p\)) whose leaf count satisfies

Let \(s\) and \(p\) be deterministic two-party communication protocols over the same input types, and suppose there is a subprotocol path from \(s\) to \(p\), witnessing that \(s\) occurs as a rooted subtree of \(p\). Then \(s\) has at most as many leaves as \(p\); that is, the number of leaves of \(s\) is less than or equal to the number of leaves of \(p\).

Let \(p\) and \(s\) be deterministic two-party communication protocols over Alice’s input type \(X\) and Bob’s input type \(Y\) with output type \(\alpha \), and let \(\pi \) be a subprotocol path witnessing that \(s\) sits at a rooted subtree of \(p\). Suppose the input pair \((x, y)\) reaches \(s\) along \(\pi \), meaning \(x\) lies in the set of Alice inputs consistent with all of Alice’s branching choices on \(\pi \) and \(y\) lies in the set of Bob inputs consistent with all of Bob’s branching choices on \(\pi \). Then executing \(p\) and executing \(s\) on \((x, y)\) yield the same output.

Let \(p\) and \(s\) be deterministic two-party communication protocols with Alice’s inputs drawn from \(X\), Bob’s inputs from \(Y\), and outputs in \(\alpha \), and suppose \(s\) is a subprotocol of \(p\), that is, a rooted subtree of \(p\). If an input pair \((x, y)\) reaches \(s\) — meaning \(x\) is consistent with every one of Alice’s branch choices and \(y\) with every one of Bob’s branch choices along the path from the root of \(p\) down to the root of \(s\) — then evaluating \(p\) on \((x, y)\) returns the same output as evaluating \(s\) on \((x, y)\).

Let \(p\) be a deterministic two-party communication protocol, and let \(s\) be a subprotocol of \(p\), witnessed by a subprotocol path recording the sequence of branch choices leading from the root of \(p\) down to the root of \(s\). Form the protocol obtained from \(p\) by collapsing the entire subtree \(s\) to a single output leaf carrying its canonical output value. Writing \(\ell (q)\) for the number of leaves (output nodes) of a protocol \(q\), the collapsed protocol has \(\ell (p) - \ell (s) + 1\) leaves, where the subtraction is truncated subtraction of natural numbers.

Let \(p\) be a deterministic two-party communication protocol over Alice’s inputs \(X\) and Bob’s inputs \(Y\), let \(s\) be a rooted subprotocol of \(p\) recorded by a subprotocol path from \(s\) to \(p\), and let \(p'\) be the protocol obtained from \(p\) by collapsing the subtree \(s\) to a single leaf carrying the canonical output of \(s\) (its leftmost leaf value). Suppose an input pair \((x,y)\), with \(x \in X\) and \(y \in Y\), does not reach \(s\): it fails to be consistent with all of Alice’s and Bob’s branch choices along the path from the root of \(p\) down to the root of \(s\). Then running \(p'\) on \((x,y)\) produces the same output as running \(p\) on \((x,y)\).

Let \(s\) and \(p\) be deterministic two-party communication protocols over the same input types \(X\), \(Y\) and output type \(\alpha \), and suppose that \(s\) is a subprotocol of \(p\), i.e. a rooted subtree of \(p\). Write \(L(q)\) for the number of leaves (output nodes) of a protocol \(q\). Erasing \(s\) from \(p\) — collapsing the subtree \(s\) to a single leaf carrying its canonical (leftmost) output value — yields a protocol whose number of leaves is

where the subtraction is truncated natural-number subtraction.

Let \(p\) be a deterministic two-party communication protocol, and let \(s\) be a subprotocol of \(p\) (a rooted subtree of \(p\)). Form the erased protocol \(\mathrm{erase}(s,p)\), obtained from \(p\) by collapsing the subtree \(s\) to a single leaf. Then for every pair of inputs \(x\) (Alice) and \(y\) (Bob) that does not reach \(s\), running the erased protocol and running \(p\) produce the same output:

Let \(s\) and \(p\) be deterministic two-party communication protocols, and suppose that \(s\) occurs as a rooted subprotocol of \(p\), witnessed by a path recording the sequence of left/right branchings from the root of \(p\) down to the root of \(s\). If \(s\) has strictly fewer leaves (output nodes) than \(p\), then splicing out the branch leading to \(s\) does not collapse the whole protocol: the result of the deletion is some protocol rather than the empty result.

Let \(s\) and \(p\) be deterministic two-party communication protocols, and suppose \(s\) occurs as a rooted subtree of \(p\), witnessed by a subprotocol path recording the branching choices from the root of \(p\) down to the root of \(s\). If \(s\) has strictly fewer leaves than \(p\), then deleting the branch leading to \(s\) yields a protocol: the splicing operation along this path is defined and produces some protocol \(q\).

Let \(p\) be a deterministic communication protocol and let \(s\) be a rooted subprotocol of \(p\), recorded by a subprotocol path running from the root of \(p\) down to the root of \(s\). Suppose that \(s\) has strictly fewer leaves than \(p\). Then splicing this path out of \(p\) does not fall into the empty root case, in which the subprotocol coincides with the whole protocol, but instead returns a genuine protocol; and that protocol is exactly the pruned protocol determined by the path together with this leaf-count hypothesis.

Let \(s\) and \(p\) be deterministic two-party communication protocols over input types \(X\) (Alice) and \(Y\) (Bob) producing values in \(\alpha \), and suppose \(s\) is a rooted subtree of \(p\), as recorded by a subprotocol path from the root of \(p\) down to the root of \(s\). If splicing that path out of \(p\) produces no protocol at all, then \(s\) is in fact all of \(p\); that is, \(s = p\).

Let \(p\) be a deterministic communication protocol and let \(s\) be a rooted subtree of \(p\), witnessed by a subprotocol path from the root of \(p\) down to the root of \(s\). Write \(\ell (r)\) for the number of leaves (output nodes) of a protocol \(r\). If deleting this branch splices out a proper subtree — that is, if the deletion produces a protocol \(q\) rather than the empty result of the root case — then

where the subtraction is truncated subtraction on \(\mathbb {N}\).

Let \(s\) and \(p\) be deterministic two-party communication protocols, and let \(s\) lie along a subprotocol path inside \(p\), so that \(s\) occurs as a rooted subtree of \(p\). If \(s\) has strictly fewer leaves than \(p\), that is, if the number of leaves of \(s\) is less than the number of leaves of \(p\), then the protocol obtained by pruning this path from \(p\) has exactly \(\text{numLeaves}(p) - \text{numLeaves}(s)\) leaves.

Let \(p\) be a deterministic two-party communication protocol with Alice inputs in \(X\) and Bob inputs in \(Y\), and let \(\pi \) be a subprotocol path witnessing that a subprotocol \(s\) is a rooted subtree of \(p\). If deleting the path \(\pi \) from \(p\) returns no protocol — which occurs precisely when the path is trivial, so that \(s = p\) — then every input pair \((x, y) \in X \times Y\) reaches \(s\) along \(\pi \), meaning \(x\) is consistent with all of Alice’s choices along \(\pi \) and \(y\) is consistent with all of Bob’s choices along \(\pi \).

Let \(p\) be a deterministic two-party communication protocol on input types \(X\) (Alice) and \(Y\) (Bob), and let \(s\) be a rooted subprotocol of \(p\) witnessed by a subprotocol path from \(s\) to \(p\). Suppose that deleting this path — splicing out the branch of \(p\) leading to \(s\) — yields a protocol \(q\) (rather than being undefined, which happens only when \(s\) is the whole of \(p\)). Then for every pair of inputs \((x,y)\) that does not reach the subprotocol \(s\) along the path — that is, \(x\) is not a reachable Alice input or \(y\) is not a reachable Bob input for that path — executing \(q\) on \((x,y)\) produces the same output as executing \(p\) on \((x,y)\).

Let \(p\) be a deterministic two-party communication protocol with Alice inputs in \(X\) and Bob inputs in \(Y\), and let \(s\) be a rooted subprotocol of \(p\), witnessed by a subprotocol path from the root of \(p\) down to the root of \(s\). Suppose \(s\) has strictly fewer leaves than \(p\), so that pruning this path yields a protocol \(p'\). Then for every input pair \((x,y)\) that does not reach \(s\) along this path — that is, \(x\) is not among the Alice inputs consistent with all of Alice’s branching choices on the path, or \(y\) is not among the Bob inputs consistent with all of Bob’s choices on it — the pruned protocol \(p'\) and the original protocol \(p\) return the same value on \((x,y)\).

Let \(p\) be a deterministic two-party communication protocol and let \(s\) be a subprotocol of \(p\), that is, a rooted subtree of \(p\). Write \(L(q)\) for the number of leaves (output nodes) of a protocol \(q\), and suppose that \(L(s) \lt L(p)\). Then the protocol obtained by pruning \(s\) out of \(p\) has exactly \(L(p) - L(s)\) leaves.

Let \(s\) and \(p\) be deterministic two-party communication protocols over Alice’s inputs \(X\), Bob’s inputs \(Y\), and output type \(\alpha \), and suppose \(s\) is a subprotocol of \(p\) (a rooted subtree) whose leaf count is strictly smaller than that of \(p\). Form the pruned protocol obtained by deleting the subtree \(s\) from \(p\). Then for every pair of inputs \(x \in X\) and \(y \in Y\) that does not reach \(s\) — that is, \((x,y)\) fails to be consistent with all of the branching choices along the path from the root of \(p\) down to \(s\) — the pruned protocol and \(p\) produce the same output on \((x,y)\): running the pruned protocol on \(x\) and \(y\) yields exactly \(p\)’s output on \(x\) and \(y\).

Let \(X\) and \(Y\) be the input types of Alice and Bob in a deterministic two-party communication protocol producing values of type \(\alpha \), and suppose \(s\) is a subprotocol of such a protocol \(p\). For any two further protocols \(q_{\mathrm{in}}\) and \(q_{\mathrm{out}}\), the test subprotocol — which spends one bit for Alice and one bit for Bob to decide whether the input reaches \(s\), then continues as \(q_{\mathrm{in}}\) if it does and as \(q_{\mathrm{out}}\) otherwise — has communication complexity

Let \(s\) be a subprotocol of a deterministic communication protocol \(p\), and let \(q_{\mathrm{in}}\) and \(q_{\mathrm{out}}\) be two further protocols on the same input types. If the input pair \((x,y)\) reaches \(s\) — that is, \(x\) lies in Alice’s reach set and \(y\) in Bob’s reach set for \(s\) — then executing the test subprotocol built from \(s\), \(q_{\mathrm{in}}\), and \(q_{\mathrm{out}}\) on \((x,y)\) yields the same output as executing \(q_{\mathrm{in}}\) on \((x,y)\).

Let \(p\) be a deterministic two-party communication protocol over Alice’s input type \(X\) and Bob’s input type \(Y\) with outputs in \(\alpha \), let \(s\) be a subprotocol of \(p\), and let \(q_{\mathrm{in}}\) and \(q_{\mathrm{out}}\) be two further such protocols. Suppose an input pair \((x, y) \in X \times Y\) does not reach \(s\); that is, \(x\) fails to lie in Alice’s reach set for \(s\), or \(y\) fails to lie in Bob’s reach set for \(s\). Then executing the test subprotocol built from \(s\), \(q_{\mathrm{in}}\), and \(q_{\mathrm{out}}\) on \((x, y)\) yields the same output as executing \(q_{\mathrm{out}}\) on \((x, y)\).

Let \(f : X \to \{ 0,1\} \) be an Alice decision function and let \(P\) assign a protocol \(P(b)\) to each bit \(b\). Then for every bit \(b\), the child \(P(b)\) is a subprotocol of the Alice node \(\texttt{alice}\; f\; P\).

Let \(f : Y \to \{ 0,1\} \) be a Bob decision function and let \(P\) assign a protocol \(P(b)\) to each bit \(b\). Then for every bit \(b\), the child \(P(b)\) is a subprotocol of the Bob node \(\texttt{bob}\; f\; P\).

Let \(p\) be a protocol, let \(P(\mathrm{false})\) and \(P(\mathrm{true})\) be two protocols that are both subprotocols of \(p\), and let \(n\) be a natural number with \(3\, (\ell (P(\mathrm{false})) + \ell (P(\mathrm{true}))) \ge 2n\), where \(\ell (\cdot )\) denotes the number of leaves. Suppose further that for each bit \(b\) with \(3\, \ell (P(b)) \ge 2n\) there is a subprotocol \(s\) of \(P(b)\) with \(n \le 3\, \ell (s) \lt 2n\). Then there is a subprotocol \(s\) of \(p\) with \(n \le 3\, \ell (s) \lt 2n\).

Let \(P\) assign a protocol to each bit, let \(b\) be a bit, and let \(s\) be a subprotocol of \(P(b)\) witnessed by a subprotocol path. If \(e = \ell (P(b)) - \ell (s) + 1\) (truncated subtraction on \(\mathbb {N}\)), then replacing the leaf count of branch \(b\) by \(e\) in the sum of the two children’s leaf counts gives

i.e. \(\ell (P(\mathrm{false})) + e = \ell (P(\mathrm{false})) + \ell (P(\mathrm{true})) - \ell (s) + 1\) when \(b = \mathrm{true}\), and \(e + \ell (P(\mathrm{true}))\) equals the same quantity when \(b = \mathrm{false}\).

Let \(s\) be a subprotocol of \(r\) via a subprotocol path \(h_s\), let \((x,y)\) be an input pair, and let \(N\) be a node constructor (an Alice or Bob node) such that for every family \(Q\) of children, running \(N(Q)\) on \((x,y)\) is the same as running \(Q(c)\) on \((x,y)\) for a fixed bit \(c\). Let \(P\) be a family of children with \(P(b) = r\), and let \(Q\) be the family obtained from \(P\) by replacing the branch \(b\) by the erasure of \(h_s\) while keeping the sibling \(Q(\neg b) = P(\neg b)\). Assume that if \((x,y)\) reaches \(s\) along the path then \(c \ne b\), and that (inductively) if \((x,y)\) does not reach \(s\) along the path then the erasure of \(h_s\) runs like \(r\) on \((x,y)\). Then \(N(Q)\) and \(N(P)\) produce the same output on \((x,y)\).

Let \(s\) be a subprotocol of \(r\) via a subprotocol path \(h_s\), let \(P\) be a family of children with \(P(b) = r\), and let \(N\) be a node constructor whose leaf count is the sum of its two children’s leaf counts. Let \(Q\) be a rebuilding map with \(Q(q_c)(b) = q_c\) and \(Q(q_c)(\neg b) = P(\neg b)\), and suppose \(q\) is the result of deleting along the path inside branch \(b\): \(q = P(\neg b)\) if the deletion of \(h_s\) returns nothing, and \(q = N(Q(q_c))\) if it returns \(q_c\). Assume (inductively) that whenever the deletion of \(h_s\) returns some \(q'\) one has \(\ell (q') = \ell (r) - \ell (s)\). Then

Let \(s\) be a subprotocol of \(r\) via a subprotocol path \(h_s\), let \((x,y)\) be an input pair, let \(P\) be a family of children with \(P(b) = r\), and let \(N\) be a node constructor such that running \(N(Q)\) on \((x,y)\) is the same as running \(Q(c)\) on \((x,y)\) for a fixed bit \(c\) and every family \(Q\). Let \(Q\) be a rebuilding map with \(Q(q_c)(b) = q_c\) and \(Q(q_c)(\neg b) = P(\neg b)\), and suppose \(q\) is the result of deleting along the path inside branch \(b\): \(q = P(\neg b)\) if the deletion of \(h_s\) returns nothing, and \(q = N(Q(q_c))\) if it returns \(q_c\). Assume that if \((x,y)\) reaches \(s\) along the path then \(c \ne b\), and (inductively) that whenever the deletion of \(h_s\) returns some \(q'\) and \((x,y)\) does not reach \(s\) along the path, \(q'\) runs like \(r\) on \((x,y)\). Then \(q\) and \(N(P)\) produce the same output on \((x,y)\).