AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol_exists

theoremverifiedimported Lean

Binary simulation of a finite-message protocol. Let $X$, $Y$, and $\alpha$ be types, and let $p$ be a finite-message two-party protocol over inputs $X$ (Alice) and $Y$ (Bob) with output type $\alpha$, in which each message ranges over an arbitrary finite nonempty type and a $\beta$-valued message is charged $\lceil \log_2 |\beta| \rceil$ bits. Then there exists a binary deterministic protocol $P$ over the same input types $X$, $Y$ and output type $\alpha$ — one in which every message is a single bit — that computes the same function, i.e.\ $P$ and $p$ return the same output on every pair of inputs, and has exactly the same communication complexity as $p$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
theorem CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol_exists
    (p : Protocol X Y α) :
    ∃ (P : Deterministic.Protocol X Y α),
      P.run = p.run ∧ P.complexity = p.complexity
Source
TCSlib, `CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol_exists`
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 12
Used by 5

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {X Y α : Type*} in/-- Every finite-message protocol is simulated by a binary protocol with the same outcome function and the same complexity. The Alice case is `encode_alice`; the Bob case is reduced to it by swapping the players. **Proof sketch.** Induction on the protocol. An output leaf is its own binary protocol. At an Alice node, the induction hypothesis chooses a binary continuation for every message; encoding the message (`encode_alice`) gives a binary protocol whose run and complexity agree with the node's. At a Bob node, swap the players in every continuation, apply the Alice case, and swap the result back; swapping preserves both run and complexity. -/theorem CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol_exists    (p : Protocol X Y α) :    ∃ (P : Deterministic.Protocol X Y α),      P.run = p.run ∧ P.complexity = p.complexity := by  induction p with  | output val => exact ⟨Deterministic.Protocol.output val, rfl, rfl⟩  | @alice β _ _ f P ih =>    choose Q hQ_run hQ_comp using ih    obtain ⟨R, hR_run, hR_comp⟩ := encode_alice f Q    exact ⟨R,      funext₂ fun x y => by rw [hR_run, hQ_run, Deterministic.FiniteMessage.Protocol.run],      by rw [hR_comp]; simp [Deterministic.FiniteMessage.Protocol.complexity, hQ_comp]⟩  | @bob β _ _ f P ih =>    choose Q hQ_run hQ_comp using ih    obtain ⟨R, hR_run, hR_comp⟩ := encode_alice f (fun b => (Q b).swap)    exact ⟨R.swap,      funext₂ fun x y => by        simp [Deterministic.FiniteMessage.Protocol.run,          Deterministic.Protocol.swap_run, hR_run, hQ_run],      by simp [Deterministic.FiniteMessage.Protocol.complexity,          Deterministic.Protocol.swap_complexity, hR_comp,          Deterministic.Protocol.swap_complexity, hQ_comp]⟩
See it in the graphDiscuss this resultChallenge it