CommunicationComplexity.Deterministic.Protocol.comap
defimported Lean
Given functions $f_X : X' \to X$ and $f_Y : Y' \to Y$, comap pulls back a protocol
$p$ over $X \times Y$ to a protocol over $X' \times Y'$ by pre-composing every message
function with $f_X$ or $f_Y$ as appropriate, leaving output nodes unchanged.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in def CommunicationComplexity.Deterministic.Protocol.comap {X' Y' : Type*} (p : Protocol X Y α) (fX : X' → X) (fY : Y' → Y) : Protocol X' Y' α
- Defined in
- TCSlib, `CommunicationComplexity.Deterministic.Protocol.comap`
- 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.Protocol.comap← CommunicationComplexity.Deterministic.Protocol.comap (TCSlib/CommunicationComplexity/DeterministicCC/DetBasic.lean:145): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 1
- 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 3
- CommunicationComplexity.Deterministic.Protocol.comap_complexityPull-back preserves communication complexity. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from…
- CommunicationComplexity.PublicCoin.Protocol.toDeterministicGiven a public-coin protocol $p$ over randomness space $\Omega$ and a fixed outcome $\omega : \Omega$,…
- CommunicationComplexity.Deterministic.Protocol.comap_runPull-back commutes with protocol execution. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from $X$…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in /-- Pull back a protocol along functions `fX : X' → X` and `fY : Y' → Y`. The resulting protocol over `X' × Y'` simulates the original by applying `fX` and `fY` to the inputs before each message function. -/ def CommunicationComplexity.Deterministic.Protocol.comap {X' Y' : Type*} (p : Protocol X Y α) (fX : X' → X) (fY : Y' → Y) : Protocol X' Y' α := match p with | .output val => .output val | .alice f P => .alice (f ∘ fX) (fun b => (P b).comap fX fY) | .bob f P => .bob (f ∘ fY) (fun b => (P b).comap fX fY)