CommunicationComplexity.Deterministic.Protocol.swap
defimported Lean
Given a protocol $p$ over $X \times Y$, swap produces a protocol over $Y \times X$
by exchanging the roles of Alice and Bob throughout: every alice node becomes a bob node
and vice versa, while output nodes are left unchanged.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in def CommunicationComplexity.Deterministic.Protocol.swap : Protocol X Y α → Protocol Y X α
- Defined in
- TCSlib, `CommunicationComplexity.Deterministic.Protocol.swap`
- 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.swap← CommunicationComplexity.Deterministic.Protocol.swap (TCSlib/CommunicationComplexity/DeterministicCC/DetBasic.lean:100): 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 4
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol_existsBinary simulation of a finite-message protocol. Let $X$, $Y$, and $\alpha$ be types, and let $p$ be a finite-message two-party protocol…
- 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.Protocol.swap_swapRole swap is an involution. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from a type $X$, Bob's…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in /-- Swaps the roles of Alice and Bob, producing a protocol on `Y × X` from one on `X × Y`. Alice nodes become bob nodes and vice versa. -/ def CommunicationComplexity.Deterministic.Protocol.swap : Protocol X Y α → Protocol Y X α | .output val => .output val | .alice f P => .bob f (fun b => (P b).swap) | .bob f P => .alice f (fun b => (P b).swap)