CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocol
defimported Lean
Embeds a binary protocol into the generalized finite-message framework by treating each
Boolean message as an element of $\beta = \mathrm{Bool}$, giving a
CommunicationComplexity.Deterministic.Protocol $X\,Y\,\alpha$ with the same tree structure.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in def CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocol : Deterministic.Protocol X Y α → Protocol X Y α
- Defined in
- TCSlib, `CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocol`
- 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.ofProtocol← CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocol (TCSlib/CommunicationComplexity/DeterministicCC/FiniteMessage.lean:325): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 2
- 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.ProtocolA deterministic two-party communication protocol over input types $X$ (Alice) and $Y$ (Bob) producing a value of type $\alpha$ is an…
- Used by 5
- 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.PublicCoin.FiniteMessage.Protocol.ofProtocolEmbeds a binary public-coin protocol into a finite-message protocol by delegating to…
- CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.ofProtocolEmbeds a binary private-coin protocol into a private-coin finite-message protocol by delegating to…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocol_complexityEmbedding binary protocols preserves complexity. Let $p$ be a deterministic binary two-party communication protocol over input types $X$…
- CommunicationComplexity.PrivateCoin.communicationComplexity_le_iff_finiteMessageFinite-message characterization of private-coin complexity. Let $f : X \to Y \to \alpha$ be a function, let $\varepsilon \in \bbr$ be an…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in /-- Embed a binary protocol into a generalized protocol (with `β = Bool` at each step). -/ def CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocol : Deterministic.Protocol X Y α → Protocol X Y α | Deterministic.Protocol.output val => Deterministic.FiniteMessage.Protocol.output val | Deterministic.Protocol.alice f P => Deterministic.FiniteMessage.Protocol.alice f (fun b => ofProtocol (P b)) | Deterministic.Protocol.bob f P => Deterministic.FiniteMessage.Protocol.bob f (fun b => ofProtocol (P b))