protocol_leaf_count
The number of leaves of a deterministic communication protocol $p$ is $1$ if $p$ is an output node, and the sum of the leaf counts of both subtrees if $p$ branches on an Alice or Bob query.
Statement
def protocol_leaf_count {X Y α : Type*} (p : CommunicationComplexity.Deterministic.Protocol X Y α) : ℕ
- Defined in
- arXiv:2611.11488, Section 1.1 and Lemma 3.2
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Built on 1
- CommunicationComplexity.Deterministic.ProtocolA deterministic two-party communication protocol over input types $X$ (Alice) and $Y$ (Bob) producing a value of type $\alpha$ is an…
- Used by 1
- min_leaf_countGiven types $X$, $Y$, and $\alpha$ and a function $f : X \to Y \to \alpha$, the minimum protocol leaf count $\mathrm{min\_leaf\_count}(f)$…
Read back from the Lean
For arbitrary types X, Y, and α, protocol_leaf_count p recursively computes the number of leaves (as a natural number ℕ) of a deterministic communication protocol p : CommunicationComplexity.Deterministic.Protocol X Y α:
- If p is an output node (CommunicationComplexity.Deterministic.Protocol.output _), it evaluates to 1.
- If p is an Alice node (CommunicationComplexity.Deterministic.Protocol.alice _ P), it evaluates to protocol_leaf_count (P false) + protocol_leaf_count (P true).
- If p is a Bob node (CommunicationComplexity.Deterministic.Protocol.bob _ P), it evaluates to protocol_leaf_count (P false) + protocol_leaf_count (P true).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The number of leaves in a deterministic communication protocol tree. -/ def protocol_leaf_count {X Y α : Type*} (p : CommunicationComplexity.Deterministic.Protocol X Y α) : ℕ := match p with | CommunicationComplexity.Deterministic.Protocol.output _ => 1 | CommunicationComplexity.Deterministic.Protocol.alice _ P => protocol_leaf_count (P false) + protocol_leaf_count (P true) | CommunicationComplexity.Deterministic.Protocol.bob _ P => protocol_leaf_count (P false) + protocol_leaf_count (P true)