AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.toCoinTape

defimported Lean

Given a public-coin finite-message protocol $p$ over an arbitrary finite probability space $\Omega$ and a slack $\delta > 0$, this definition produces a natural number $n$ together with a finite-message protocol over $\mathrm{CoinTape}(n)$ that approximates $p$. The construction works by pulling back $p$ along a measure-approximating map $\varphi : \mathrm{CoinTape}(n) \to \Omega$ provided by CommunicationComplexity.Internal.single_coin_approx.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory in
noncomputable def CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.toCoinTape
    {Ω : Type*} [FiniteProbabilitySpace Ω]
    {X Y α : Type*}
    (p : FiniteMessage.Protocol Ω X Y α)
    (δ : ℝ) (hδ : 0 < δ) :
    Σ (n : ℕ), FiniteMessage.Protocol (CoinTape n) X Y α
Defined in
TCSlib, `CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.toCoinTape`
Lean proof
By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
16 Oct 2026
Axioms
none listed
Built on 28
Used by 1

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory in
/-- The coin-tape approximation of a public-coin finite-message protocol `p` over an arbitrary finite probability space `Ω` with slack `δ > 0`: a length `n` together with a protocol over `CoinTape n` obtained by pulling `p` back along a map `φ : CoinTape n → Ω` (chosen by `Internal.single_coin_approx`) under which every event of `Ω` is approximated to within `δ`. The result has the same complexity as `p` and, on every input, an error probability at most `δ` larger. -/
noncomputable def CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.toCoinTape
    {Ω : Type*} [FiniteProbabilitySpace Ω]
    {X Y α : Type*}
    (p : FiniteMessage.Protocol Ω X Y α)
    (δ : ℝ) (hδ : 0 < δ) :
    Σ (n : ℕ), FiniteMessage.Protocol (CoinTape n) X Y α :=
  let data := Internal.single_coin_approx (Ω := Ω) δ hδ
  let n := data.choose
  let φ := data.choose_spec.choose
  ⟨n, p.comap (Prod.map φ id) (Prod.map φ id)⟩
See it in the graphDiscuss this resultChallenge it