AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.rrun_eq

theoremverifiedimported Lean

Explicit-coin execution as paired-input execution. Let $p$ be a private-coin finite-message protocol over input types $X$, $Y$, with private-randomness types $\Omega_X$, $\Omega_Y$ and output type $\alpha$. For all inputs $x : X$ and $y : Y$ and all private coins $\omega_x : \Omega_X$ and $\omega_y : \Omega_Y$, executing $p$ with those explicit coins agrees with executing the underlying deterministic finite-message protocol on the paired inputs $(\omega_x, x)$ for Alice and $(\omega_y, y)$ for Bob; that is, both yield the same element of $\alpha$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory in
variable {Ω_X Ω_Y : Type*} {X Y α : Type*} in
@[simp]
theorem CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.rrun_eq (p : Protocol Ω_X Ω_Y X Y α) (x : X) (y : Y)
    (ω_x : Ω_X) (ω_y : Ω_Y) :
    p.rrun x y ω_x ω_y = p.run (ω_x, x) (ω_y, y)
Source
TCSlib, `CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.rrun_eq`
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
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 14
Used by 26

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory in
variable {Ω_X Ω_Y : Type*} {X Y α : Type*} in
/-- Running a private-coin finite-message protocol on inputs `x`, `y` with randomness `ω_x`, `ω_y` is the same as running the underlying deterministic finite-message protocol on `(ω_x, x)` and `(ω_y, y)`. Definitional unfolding lemma for `rrun`. -/
@[simp]
theorem CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.rrun_eq (p : Protocol Ω_X Ω_Y X Y α) (x : X) (y : Y)
    (ω_x : Ω_X) (ω_y : Ω_Y) :
    p.rrun x y ω_x ω_y = p.run (ω_x, x) (ω_y, y) := rfl
See it in the graphDiscuss this resultChallenge it