AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.PublicCoin.zeroErrorCommunicationComplexity

def

For types X, Y, and α, and a function f : X → Y → α, the zero-error public-coin expected communication complexity is defined as the infimum (sInf) in ℝ of the set of all real numbers r such that there exists a natural number n and a protocol p : PublicCoin.Protocol (CoinTape n) X Y α satisfying p.ApproxComputes f 0 and for all x : X and y : Y, the integral over ω : CoinTape n with respect to volume of p.length (ω, x) (ω, y) cast to ℝ is at most r.

Statement

open MeasureTheory in
noncomputable def CommunicationComplexity.PublicCoin.zeroErrorCommunicationComplexity
    {X Y α : Type*} (f : X → Y → α) : ℝ
Defined in
arXiv:2611.11488 Section 5.2, equation (5.1)
Verified
10 Nov 2026
Axioms
none listed
Built on 5

Read back from the Lean

The zero-error public-coin communication complexity of a function f : X → Y → α is defined as the real infimum (sInf) of the set of all r : ℝ such that there exists a natural number n and a public-coin protocol p : PublicCoin.Protocol (CoinTape n) X Y α satisfying: 1. p.ApproxComputes f 0 (protocol p computes f with error parameter 0), and 2. For all inputs x : X and y : Y, the Bochner integral (with respect to the default volume measure on CoinTape n) of the execution length (p.length (ω, x) (ω, y) : ℝ) over all random coin tapes ω : CoinTape n is at most r.

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

open MeasureTheory in
/-- Zero-error public-coin expected communication complexity. -/
noncomputable def CommunicationComplexity.PublicCoin.zeroErrorCommunicationComplexity
    {X Y α : Type*} (f : X → Y → α) : ℝ := sInf { r : ℝ | ∃ (n : ℕ) (p : PublicCoin.Protocol (CoinTape n) X Y α),
    p.ApproxComputes f 0 ∧
    ∀ (x : X) (y : Y), (∫ (ω : CoinTape n), (p.length (ω, x) (ω, y) : ℝ)) ≤ r }
See it in the graphDiscuss this resultChallenge it