Let \(p\) be a deterministic two-party communication protocol over input types \(X\) (Alice) and \(Y\) (Bob) with output type \(\alpha \). Then the number of leaves of \(p\) — that is, the number of output nodes in its tree shape — is strictly positive, and so is at least one.

Let \(p\) be a deterministic two-party communication protocol over input types \(X\) and \(Y\) with output type \(\alpha \). If \(p\) has exactly one leaf, that is, if the number of output nodes of \(p\) equals \(1\), then the communication complexity of \(p\) is \(0\).

Let \(m, n \in \mathbb {N}\) satisfy \(3m \le 2n\) and \(3(n - m) \le 2n\), so that neither of the two parts \(m\) and \(n - m\) exceeds two-thirds of \(n\). Then

Let \(s, p, q_{\mathrm{in}}, q_{\mathrm{out}}\) be deterministic two-party protocols over input types \(X\) and \(Y\) with outputs in \(\alpha \), where \(s\) is a subprotocol of \(p\) with strictly fewer leaves than \(p\). Suppose \(q_{\mathrm{in}}\) computes the same function as \(s\), and \(q_{\mathrm{out}}\) computes the same function as the protocol obtained from \(p\) by pruning \(s\) away. Then the glued protocol CommunicationComplexity.Deterministic.Protocol.testSubprotocol, which first tests whether the inputs reach \(s\) and then runs \(q_{\mathrm{in}}\) or \(q_{\mathrm{out}}\) accordingly, computes the same function as \(p\) on every pair of inputs \((x,y)\).

Let \(c_{\mathrm{in}}, c_{\mathrm{out}}, m, n \in \mathbb {N}\) satisfy the two inductive bounds \(3^{c_{\mathrm{in}}} \le 2^{c_{\mathrm{in}}} m^2\) and \(3^{c_{\mathrm{out}}} \le 2^{c_{\mathrm{out}}} (n - m)^2\), together with the balance conditions \(3m \le 2n\) and \(3(n - m) \le 2n\). Then, writing \(c = 2 + \max (c_{\mathrm{in}}, c_{\mathrm{out}})\),