AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.Protocol.length

def

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
Used by 2

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
See it in the graphDiscuss this resultChallenge it