CommunicationComplexity.Deterministic.Protocol.comap_run
theoremverifiedimported Lean
Pull-back commutes with protocol execution. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from $X$ and Bob's from $Y$, producing values in $\alpha$, and let $f_X : X' \to X$ and $f_Y : Y' \to Y$ be arbitrary maps of input types. Then for all $x' \in X'$ and $y' \in Y'$, running the pull-back of $p$ along $f_X$ and $f_Y$ on the inputs $x'$ and $y'$ yields the same output as running $p$ itself on the transported inputs $f_X(x')$ and $f_Y(y')$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in @[simp] theorem CommunicationComplexity.Deterministic.Protocol.comap_run {X' Y' : Type*} (p : Protocol X Y α) (fX : X' → X) (fY : Y' → Y) (x' : X') (y' : Y') : (p.comap fX fY).run x' y' = p.run (fX x') (fY y')
- Source
- TCSlib, `CommunicationComplexity.Deterministic.Protocol.comap_run`
- 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_run← CommunicationComplexity.Deterministic.Protocol.comap_run (TCSlib/CommunicationComplexity/DeterministicCC/DetBasic.lean:154): verbatim
- Verified
- 07 Oct 2026
- Axioms
propext- Built on 6
- 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.Protocol.runGiven a protocol $p$,
runevaluates $p$ on inputs $x : X$ and $y : Y$ by recursively following the bit-branching structure until… - CommunicationComplexity.Deterministic.FiniteMessage.Protocol.comap_runExecution commutes with pullback. Let $p$ be a finite-message deterministic communication protocol over input types $X$, $Y$ with output…
- CommunicationComplexity.Deterministic.Protocol.comapGiven functions $f_X : X' \to X$ and $f_Y : Y' \to Y$,
comappulls back a protocol $p$ over $X \times Y$ to a protocol over… - 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.Deterministic.Protocol.aux_monoLeaf rectangles are output-monochromatic. Let $p$ be a deterministic communication protocol over input types $X$ (Alice) and $Y$ (Bob)…
- Used by 35
- CommunicationComplexity.PrivateCoin.communicationComplexity_le_iffCharacterization of private-coin complexity by upper bounds. Let $f : X \to Y \to \alpha$ be a function, let $\varepsilon \in \bbr$ be an…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocolGiven a public-coin finite-message protocol $p$ over a probability space $\Omega$ that $\varepsilon$-computes $f : X \to Y \to \alpha$,…
- CommunicationComplexity.PublicCoin.communicationComplexity_le_iffBit bound as existence of an approximating protocol. Let $f : X \to Y \to \alpha$ be a function of Alice's input and Bob's input, let…
- CommunicationComplexity.PrivateCoin.communicationComplexity_le_of_finiteMessageFinite-probability protocols bound private-coin complexity. Let $X$, $Y$, and $\alpha$ be types, let $f : X \to Y \to \alpha$ be the…
- CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.toProtocol_rrunExecution is preserved under conversion to a binary private-coin protocol. Let $p$ be a private-coin finite-message protocol with…
- CommunicationComplexity.PublicCoin.Protocol.toDeterministic_runFixing the shared randomness agrees with the randomised run. Let $p$ be a public-coin protocol over a randomness space $\Omega$, with…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.exists_good_randomnessExistence of good randomness for derandomization. Let $\Omega$ be a finite probability space and let $X$ and $Y$ be finite input sets. Let…
- CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.ofProtocol_complexityEmbedding a binary private-coin protocol preserves complexity. Let $p$ be a binary private-coin protocol with randomness spaces $\Omega_X$…
- CommunicationComplexity.PublicCoin.Protocol.toDeterministic_complexityFixing shared randomness preserves communication complexity. Let $p$ be a public-coin communication protocol over a shared randomness…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.toCoinTape_complexityCoin-tape conversion preserves complexity. Let $\Omega$ be a finite probability space, and let $p$ be a public-coin finite-message…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.toDeterministic_complexityFixing shared randomness preserves communication complexity. Let $p$ be a public-coin finite-message protocol over a shared-randomness…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.ofProtocol_rrunEmbedding preserves randomized execution. Let $\Omega$ be a shared-randomness space, let $X$ and $Y$ be the private input sets of the two…
- CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.rrun_eqExplicit-coin execution as paired-input execution. Let $p$ be a private-coin finite-message protocol over input types $X$, $Y$, with…
- CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.ofProtocol_rrunEmbedding preserves randomized execution of private-coin protocols. The embedding of a binary private-coin protocol into the…
- CommunicationComplexity.PublicCoin.Protocol.rrun_eqRandomized execution as deterministic execution on paired inputs. Let $p$ be a public-coin protocol with shared randomness in $\Omega$,…
- CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.toProtocolConverts a private-coin finite-message protocol into a binary-tree private-coin protocol by delegating to…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toPrivateCoin_complexityComplexity is preserved by passage to the private-coin model. Let $p$ be a deterministic finite-message protocol over input types $X$, $Y$…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.toProtocolConverts a public-coin finite-message protocol to a binary public-coin protocol by delegating to…
- CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.toCoinTapeGiven a finite-message private-coin protocol $p$ over finite probability spaces $\Omega_X$ and $\Omega_Y$, and a tolerance $\delta > 0$,…
- CommunicationComplexity.PrivateCoin.Protocol.rrun_eqRandomized execution as deterministic run on paired inputs. Let $p$ be a private-coin protocol with randomness spaces $\Omega_X$ and…
- CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.toCoinTape_approxSatisfiesCoin-tape conversion preserves approximate correctness. Let $p$ be a private-coin finite-message protocol over input types $X$, $Y$ and…
- CommunicationComplexity.PrivateCoin.communicationComplexityThe $\varepsilon$-error private-coin randomized communication complexity of $f : X \to Y \to \alpha$ is the extended natural number…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol_ApproxComputesNewman's reduction preserves approximate correctness. Let $\Omega$ be a finite probability space, let $X$ and $Y$ be finite types, and let…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.toProtocol_rrunBinary conversion preserves randomized execution. Let $p$ be a public-coin finite-message protocol with shared-randomness space $\Omega$,…
- 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…
- CommunicationComplexity.PublicCoin.Protocol.toDeterministicGiven a public-coin protocol $p$ over randomness space $\Omega$ and a fixed outcome $\omega : \Omega$,…
- CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.toProtocol_complexityComplexity is preserved by the binary conversion. Let $p$ be a private-coin finite-message protocol with private randomness spaces…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.toProtocol_complexityConversion to a binary public-coin protocol preserves communication complexity. Let $\Omega$ be a shared-randomness space and let $p$ be a…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol_complexityCommunication cost of the Newman protocol. Let $X$ and $Y$ be finite types, let $\Omega$ be a finite probability space, and let $p$ be a…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.toDeterministic_runFixing randomness commutes with execution. Let $p$ be a public-coin finite-message protocol over a shared-randomness space $\Omega$,…
- CommunicationComplexity.PublicCoin.communicationComplexityThe $\varepsilon$-error public-coin randomized communication complexity of $f : X \to Y \to \alpha$ is defined as…
- CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.toCoinTape_complexityCoin-tape conversion preserves communication complexity. Let $\Omega_X$ and $\Omega_Y$ be finite probability spaces, let $X$, $Y$ be input…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.ofProtocol_complexityComplexity invariance of the finite-message embedding. Let $\Omega$ be a shared-randomness space, let $X$ and $Y$ be the private input…
- CommunicationComplexity.PublicCoin.newmanNewman's theorem for communication complexity. Let $X$ and $Y$ be finite types, let $f : X \to Y \to \alpha$, and let…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.toCoinTapeGiven a public-coin finite-message protocol $p$ over an arbitrary finite probability space $\Omega$ and a slack $\delta > 0$, this…
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/-- Running the pulled-back protocol on `(x', y')` gives the same output as running the original protocol on `(fX x', fY y')`. -/@[simp]theorem CommunicationComplexity.Deterministic.Protocol.comap_run {X' Y' : Type*} (p : Protocol X Y α) (fX : X' → X) (fY : Y' → Y) (x' : X') (y' : Y') : (p.comap fX fY).run x' y' = p.run (fX x') (fY y') := by induction p <;> simp [comap, run, *]