min_leaf_count
Given types $X$, $Y$, and $\alpha$ and a function $f : X \to Y \to \alpha$, the minimum protocol leaf count $\mathrm{min\_leaf\_count}(f)$ is the extended natural number in $\mathrm{ENat}$ defined as the infimum of $\mathrm{protocol\_leaf\_count}(p)$ over all deterministic communication protocols $p : \mathrm{CommunicationComplexity.Deterministic.Protocol}\;X\;Y\;\alpha$ satisfying $p.\mathrm{Computes}\;f$.
Statement
noncomputable def min_leaf_count {X Y α : Type*} (f : X → Y → α) : ENat
- Defined in
- arXiv:2611.11488, Section 1.1 and Section 5.1
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Built on 3
- protocol_leaf_countThe 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…
- CommunicationComplexity.Deterministic.ProtocolA deterministic two-party communication protocol over input types $X$ (Alice) and $Y$ (Bob) producing a value of type $\alpha$ is an…
- CommunicationComplexity.Deterministic.Protocol.ComputesA protocol $p$ computes a two-argument function $f : X \to Y \to \alpha$ if $p.\texttt{run}\,x\,y = f\,x\,y$ for all inputs $x : X$…
Read back from the Lean
For types X, Y, and α, and a function f : X → Y → α, min_leaf_count f is defined as the infimum in ENat (the extended natural numbers $\mathbb{N} \cup \{\infty\}$) of (protocol_leaf_count p : ENat) taken over all deterministic communication protocols p : CommunicationComplexity.Deterministic.Protocol X Y α satisfying p.Computes f.
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 minimum number of leaves in any correct deterministic protocol computing f. -/ noncomputable def min_leaf_count {X Y α : Type*} (f : X → Y → α) : ENat := ⨅ (p : CommunicationComplexity.Deterministic.Protocol X Y α) (_ : p.Computes f), (protocol_leaf_count p : ENat)