CommunicationComplexity.Deterministic.Protocol.complexity
defimported Lean
The communication complexity of a protocol $p$ is the worst-case total number of bits exchanged: an output node costs $0$, while an alice or bob node costs $1$ plus the maximum complexity of the two sub-protocols reached by the bit $\mathtt{false}$ and the bit $\mathtt{true}$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in def CommunicationComplexity.Deterministic.Protocol.complexity : Protocol X Y α → ℕ
- Defined in
- TCSlib, `CommunicationComplexity.Deterministic.Protocol.complexity`
- 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.complexity← CommunicationComplexity.Deterministic.Protocol.complexity (TCSlib/CommunicationComplexity/DeterministicCC/DetBasic.lean:82): 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 32
- CommunicationComplexity.Deterministic.communicationComplexity_le_iffThreshold characterization of deterministic communication complexity. Let $f : X \to Y \to \alpha$ be a two-argument function and let $n$…
- 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.Deterministic.le_communicationComplexity_iffLower-bound characterization of communication complexity. Let $f : X \to Y \to \alpha$ be a two-argument function, let…
- 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.Deterministic.FiniteMessage.Protocol.completeTreeAlice_complexityComplexity of the complete Alice-query tree. Fix a natural number $d$, together with binary query functions…
- 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.Deterministic.Protocol.aux_cardLeaf rectangle count bounded by two to the complexity. Let $p$ be a deterministic two-party communication protocol with input types $X$…
- CommunicationComplexity.PublicCoin.Protocol.toDeterministic_complexityFixing shared randomness preserves communication complexity. Let $p$ be a public-coin communication protocol over a shared randomness…
- 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.Protocol.logb_le_complexity_of_distributionalErrorDiscrepancy lower bound on communication complexity. Let $\mu$ be a finite probability space on $X \times Y$, let…
- 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.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.one_sub_two_distributionalError_le_two_pow_mulDiscrepancy lower bound on distributional error. Let $\mu$ be a finite probability measure on $X \times Y$, let…
- 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.communicationComplexityThe deterministic communication complexity of $f : X \to Y \to \alpha$ is defined as…
- CommunicationComplexity.PrivateCoin.communicationComplexityThe $\varepsilon$-error private-coin randomized communication complexity of $f : X \to Y \to \alpha$ is the extended natural number…
- 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.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.Deterministic.foolingSet_ncard_le_pow_of_communicationComplexity_leFooling set bound from communication complexity. Let $g : X \times Y \to \alpha$ be a two-argument function, and let…
- 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.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.Functions.Equality.communicationComplexity_zeroDeterministic complexity of equality at $n = 0$. Let…
- CommunicationComplexity.Deterministic.communicationComplexity_le_of_finiteMessage_protocolUpper bound witnessed by a finite-message protocol. Let $f : X \to Y \to \alpha$ and let $p$ be a finite-message protocol over $X$, $Y$,…
- CommunicationComplexity.PublicCoin.communicationComplexityThe $\varepsilon$-error public-coin randomized communication complexity of $f : X \to Y \to \alpha$ is defined as…
- CommunicationComplexity.Deterministic.mono_partition_of_communicationComplexity_leLow deterministic complexity yields a small monochromatic partition. Let $g : X \times Y \to \alpha$ be a two-argument function, and let…
- 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.Deterministic.Protocol.leafRectangles_cardLeaf rectangle count is at most two to the complexity. Let $p$ be a deterministic two-party communication protocol over input types $X$…
- 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.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.le_communicationComplexity_of_forall_lt_ncardRectangle-partition lower bound on communication complexity. Let $g : X \to Y \to \alpha$ be a two-argument function and let $n$ be a…
- 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
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in /-- The communication complexity of a protocol, i.e. the worst-case number of bits exchanged, which is the depth of the protocol tree. [RY20, Ch. 1, Definition (computing a function, complexity, rounds)]. -/ def CommunicationComplexity.Deterministic.Protocol.complexity : Protocol X Y α → ℕ | .output _ => 0 | .alice _ P => 1 + max (P false).complexity (P true).complexity | .bob _ P => 1 + max (P false).complexity (P true).complexity