AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocol_complexity

theoremverifiedimported Lean

Embedding binary protocols preserves complexity. Let $p$ be a deterministic binary two-party communication protocol over input types $X$ and $Y$ with output type $\alpha$, and let its embedding into the finite-message framework send each Boolean message as an element of $\{\mathtt{false},\mathtt{true}\}$. Then the communication complexity of the embedded finite-message protocol equals the communication complexity of $p$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
theorem CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocol_complexity (p : Deterministic.Protocol X Y α) :
    (ofProtocol p).complexity = p.complexity
Source
TCSlib, `CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocol_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
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
Used by 5

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {X Y α : Type*} in/-- Viewing a binary protocol as a finite-message protocol does not change its complexity: each `Bool`-valued message costs `⌈log₂ 2⌉ = 1` bit. -/theorem CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocol_complexity (p : Deterministic.Protocol X Y α) :    (ofProtocol p).complexity = p.complexity := by  induction p <;> simp only [ofProtocol, complexity,    Deterministic.Protocol.complexity, Fintype.univ_bool,    Finset.sup_insert, Finset.sup_singleton,    Fintype.card_bool, clog_two_two,    Nat.max_comm, *]
See it in the graphDiscuss this resultChallenge it