AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.ofProtocol_rrun

theoremverifiedimported Lean

Embedding preserves randomized execution of private-coin protocols. The embedding of a binary private-coin protocol into the finite-message framework does not change what the protocol computes. Let $p$ be a binary private-coin communication protocol with input spaces $X$ and $Y$, private-randomness spaces $\Omega_X$ and $\Omega_Y$, and output type $\alpha$, and let $\widehat{p}$ be the finite-message private-coin protocol obtained by embedding $p$ (interpreting each Boolean message as an element of a two-element message alphabet). Then for every pair of inputs $x \in X$, $y \in Y$ and every pair of private coins $\omega_x \in \Omega_X$, $\omega_y \in \Omega_Y$, the randomized execution of $\widehat{p}$ agrees with that of $p$: \[ \widehat{p}\text{'s output on }(x, y, \omega_x, \omega_y) \;=\; p\text{'s output on }(x, y, \omega_x, \omega_y). \]

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.ofProtocol_rrun
    (p : PrivateCoin.Protocol Ω_X Ω_Y X Y α)
    (x : X) (y : Y) (ω_x : Ω_X) (ω_y : Ω_Y) :
    (ofProtocol p).rrun x y ω_x ω_y = p.rrun x y ω_x ω_y
Source
TCSlib, `CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.ofProtocol_rrun`
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 19
Used by 6

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen MeasureTheory invariable {Ω_X Ω_Y : Type*} {X Y α : Type*} in/-- The finite-message protocol obtained from a binary private-coin protocol `p` by `ofProtocol` has the same output as `p` on every input `x`, `y` and every pair of random strings `ω_x`, `ω_y`. -/@[simp]theorem CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.ofProtocol_rrun    (p : PrivateCoin.Protocol Ω_X Ω_Y X Y α)    (x : X) (y : Y) (ω_x : Ω_X) (ω_y : Ω_Y) :    (ofProtocol p).rrun x y ω_x ω_y = p.rrun x y ω_x ω_y := by  simp [rrun, PrivateCoin.Protocol.rrun,    Deterministic.FiniteMessage.Protocol.ofProtocol_run]
See it in the graphDiscuss this resultChallenge it