AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.PrivateCoin.zeroErrorCommunicationComplexity

def

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

Statement

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

Read back from the Lean

Given types X, Y, and α, and a function f : X → Y → α, CommunicationComplexity.PrivateCoin.zeroErrorCommunicationComplexity f is defined as the infimum (sInf) of the set of all real numbers r : ℝ such that there exist natural numbers nX and nY and a protocol p : PrivateCoin.Protocol (CoinTape nX) (CoinTape nY) X Y α satisfying: 1. p.ApproxComputes f 0 (the protocol p computes f with error bound 0), and 2. for all x : X and y : Y, the integral over ω : CoinTape nX × CoinTape nY (with respect to the default volume measure) of the protocol execution length (p.length (ω.1, x) (ω.2, y) : ℝ) is less than or equal to 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 private-coin expected communication complexity. -/
noncomputable def CommunicationComplexity.PrivateCoin.zeroErrorCommunicationComplexity
    {X Y α : Type*} (f : X → Y → α) : ℝ := sInf { r : ℝ | ∃ (nX nY : ℕ) (p : PrivateCoin.Protocol (CoinTape nX) (CoinTape nY) X Y α),
    p.ApproxComputes f 0 ∧
    ∀ (x : X) (y : Y), (∫ (ω : CoinTape nX × CoinTape nY), (p.length (ω.1, x) (ω.2, y) : ℝ)) ≤ r }
See it in the graphDiscuss this resultChallenge it