AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toPrivateCoin_complexity

theoremverifiedimported Lean

Complexity is preserved by passage to the private-coin model. Let $p$ be a deterministic finite-message protocol over input types $X$, $Y$ and output type $\alpha$, and let $\Omega_X$, $\Omega_Y$ be arbitrary types to serve as private-randomness spaces. Form the private-coin finite-message protocol over $\Omega_X$, $\Omega_Y$ obtained from $p$ by having each player ignore their private coin, so that Alice's message function $f : X \to \beta$ is replaced by $(\omega, x) \mapsto f(x)$ and Bob's by $(\omega, y) \mapsto f(y)$, with the protocol tree otherwise unchanged. Then this private-coin protocol has the same communication complexity as $p$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory in
@[simp]
theorem CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toPrivateCoin_complexity
    {X Y α Ω_X Ω_Y : Type*}
    (p : Deterministic.FiniteMessage.Protocol X Y α) :
    (p.toPrivateCoin (Ω_X := Ω_X) (Ω_Y := Ω_Y)).complexity =
      p.complexity
Source
TCSlib, `CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toPrivateCoin_complexity`
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
Classical.choiceQuot.soundpropext
Built on 21
Used by 1

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory in
/-- Viewing a deterministic finite-message protocol as a private-coin protocol does not change its complexity. -/
@[simp]
theorem CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toPrivateCoin_complexity
    {X Y α Ω_X Ω_Y : Type*}
    (p : Deterministic.FiniteMessage.Protocol X Y α) :
    (p.toPrivateCoin (Ω_X := Ω_X) (Ω_Y := Ω_Y)).complexity =
      p.complexity := by
  simp [toPrivateCoin]
See it in the graphDiscuss this resultChallenge it