CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol_exists
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.CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol_exists← CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol_exists (TCSlib/CommunicationComplexity/DeterministicCC/FiniteMessage.lean:278): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- CommunicationComplexity.Deterministic.Protocol.complexityThe communication complexity of a protocol $p$ is the worst-case total number of bits exchanged: an output node costs $0$, while an alice…
- CommunicationComplexity.Deterministic.FiniteMessage.ProtocolA generalized deterministic two-party communication protocol over input types $X$, $Y$ and output type $\alpha$. At each step a player…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.runGiven a finite-message protocol $p$ and inputs $x : X$, $y : Y$,
runexecutes $p$ recursively: at analicenode it… - CommunicationComplexity.Deterministic.Protocol.swapGiven a protocol $p$ over $X \times Y$,
swapproduces a protocol over $Y \times X$ by exchanging the roles of Alice and Bob… - CommunicationComplexity.Deterministic.FiniteMessage.Protocol.complexityThe worst-case communication cost of a finite-message protocol, measured in bits. An
outputnode costs $0$; analiceor… - CommunicationComplexity.Deterministic.ProtocolA deterministic two-party communication protocol over input types $X$ (Alice) and $Y$ (Bob) producing a value of type $\alpha$ is an…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.encode_aliceBinary encoding of a finite-alphabet message from Alice. Let $X$, $Y$, and $\alpha$ be types, let $\beta$ be a finite nonempty type, let…
- CommunicationComplexity.Deterministic.Protocol.runGiven a protocol $p$,
runevaluates $p$ on inputs $x : X$ and $y : Y$ by recursively following the bit-branching structure until… - CommunicationComplexity.Deterministic.Protocol.swap_runRole swap preserves protocol output. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from $X$, Bob's…
- CommunicationComplexity.Deterministic.Protocol.swap_complexityRole swap preserves communication complexity. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from a…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocol_runEmbedding preserves protocol output. Let $X$ and $Y$ be the input types of Alice and Bob, let $\alpha$ be an output type, and let $p$ be a…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocol_complexityEmbedding binary protocols preserves complexity. Let $p$ be a deterministic binary two-party communication protocol over input types $X$…
- Used by 5
- CommunicationComplexity.Deterministic.communicationComplexity_le_clog_card_X_alphaTrivial upper bound on deterministic communication complexity. Let $X$ and $\alpha$ be finite nonempty types, let $Y$ be an arbitrary…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocolA noncomputable function that converts a finite-message protocol $p$ into a binary protocol…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol_runConversion to binary protocol preserves output. Let $p$ be a finite-message deterministic two-party protocol over input types $X$ and $Y$…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.comap_complexityPullback preserves communication complexity. Let $p$ be a finite-message deterministic communication protocol over input types $X$ and $Y$…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol_complexityConversion to a binary protocol preserves complexity. Let $p$ be a finite-message deterministic two-party communication protocol over…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]⟩