CommunicationComplexity.Deterministic.Protocol.length
For a deterministic two-party protocol p and inputs x and y, the transcript length p.length x y is the number of bits communicated by the parties on input (x, y).
Statement
def CommunicationComplexity.Deterministic.Protocol.length {X Y α : Type*} : CommunicationComplexity.Deterministic.Protocol X Y α → X → Y → ℕ
- Defined in
- arXiv:2611.11488 Section 5.2, page 19
- 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 2
- CommunicationComplexity.PublicCoin.zeroErrorCommunicationComplexityFor types X, Y, and α, and a function f : X → Y → α, the zero-error public-coin expected communication complexity is defined as the…
- CommunicationComplexity.PrivateCoin.zeroErrorCommunicationComplexityFor types X, Y, and α, and a function f : X → Y → α, the zero-error private-coin expected communication complexity is defined as the…
Read back from the Lean
Given arbitrary types X, Y, and α, CommunicationComplexity.Deterministic.Protocol.length defines a function taking a protocol p : CommunicationComplexity.Deterministic.Protocol X Y α and inputs x : X and y : Y, and returning a natural number ℕ representing the length / number of communication steps of p on input (x, y).
It is defined recursively on p by:
1. If p = .output _, the length is 0.
2. If p = .alice f k (where Alice applies function f to her input x, selecting the continuation protocol k (f x)), the length is 1 + length (k (f x)) x y.
3. If p = .bob g k (where Bob applies function g to his input y, selecting the continuation protocol k (g y)), the length is 1 + length (k (g y)) x y.
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 transcript length of a deterministic protocol on a given pair of inputs. -/ def CommunicationComplexity.Deterministic.Protocol.length {X Y α : Type*} : CommunicationComplexity.Deterministic.Protocol X Y α → X → Y → ℕ := fun p x y => match p with | .output _ => 0 | .alice f k => 1 + length (k (f x)) x y | .bob g k => 1 + length (k (g y)) x y