CommunicationComplexity.Deterministic.communicationComplexity
defimported Lean
The deterministic communication complexity of $f : X \to Y \to \alpha$ is defined as \[ D(f) \;=\; \inf_{\substack{p \;:\; \mathrm{Protocol}\;X\;Y\;\alpha \\ p \text{ computes } f}} p.\mathrm{complexity} \;\in\; \mathbb{N}_\infty. \] The infimum is taken over all deterministic protocols $p$ that compute $f$, and the result lives in $\mathrm{ENat}$ to accommodate the case where no finite protocol exists.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in noncomputable def CommunicationComplexity.Deterministic.communicationComplexity {X Y α : Type*} (f : X → Y → α) : ENat
- Defined in
- TCSlib, `CommunicationComplexity.Deterministic.communicationComplexity`
- 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.communicationComplexity← CommunicationComplexity.Deterministic.communicationComplexity (TCSlib/CommunicationComplexity/DeterministicCC/DetComplexity.lean:86): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 3
- CommunicationComplexity.Deterministic.Protocol.complexityThe communication complexity of a protocol $p$ is the worst-case total number of bits exchanged: an output node costs $0$, while an alice…
- 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.ComputesA protocol $p$ computes a two-argument function $f : X \to Y \to \alpha$ if $p.\texttt{run}\,x\,y = f\,x\,y$ for all inputs $x : X$…
- Used by 18
- 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.Deterministic.le_communicationComplexity_iffLower-bound characterization of communication complexity. Let $f : X \to Y \to \alpha$ be a two-argument function, let…
- CommunicationComplexity.Deterministic.communicationComplexity_le_clog_card_X_alphaTrivial upper bound on deterministic communication complexity. Let $X$ and $\alpha$ be finite nonempty types, let $Y$ be an arbitrary…
- CommunicationComplexity.Functions.Disjointness.communicationComplexity_eqDeterministic complexity of set disjointness. Let $n \geq 1$, and let $\mathrm{disjointness}(n, \cdot, \cdot)$ denote the two-party…
- CommunicationComplexity.Deterministic.Rank.clog_boolFunctionRank_le_communicationComplexityLog-rank lower bound on deterministic communication complexity. Let $X$ be a finite type and $Y$ a finite type, and let…
- CommunicationComplexity.Functions.Equality.le_communicationComplexityDeterministic complexity lower bound for equality. For every natural number $n \ge 1$, the deterministic communication complexity of the…
- CommunicationComplexity.Deterministic.clog_ncard_le_communicationComplexityFooling-set lower bound for deterministic communication complexity. Let $g : X \times Y \to \alpha$ be a two-argument function and let…
- CommunicationComplexity.Functions.Indexing.le_oneWayCommunicationComplexityOne-way complexity of Index is at least $n$. Every correct deterministic one-way protocol for $\mathrm{IND}_n$ has cost at least $n$; that…
- CommunicationComplexity.Functions.Disjointness.communicationComplexity_leUpper bound on the communication complexity of disjointness. Fix $n \in \bbn$, and let both players' inputs range over subsets of…
- CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_pow_of_communicationComplexity_leRank bound from communication complexity. Let $X$ and $Y$ be finite types and let $f : X \to Y \to \mathrm{Bool}$ be a two-party Boolean…
- CommunicationComplexity.Functions.Equality.communicationComplexity_eqExact deterministic complexity of equality. For a natural number $n$, let $\mathrm{equality}_n$ denote the two-party Boolean function on…
- CommunicationComplexity.Functions.Equality.communicationComplexity_leDeterministic complexity upper bound for equality. For every natural number $n$, the deterministic communication complexity of the $n$-bit…
- 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.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.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.Functions.Disjointness.le_communicationComplexityLower bound on the communication complexity of disjointness. Fix an integer $n \ge 1$, and consider the set-disjointness function on…
- 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…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in /-- The deterministic communication complexity of `f : X → Y → α`: the minimum, over all protocols computing `f`, of the protocol's complexity (worst-case number of bits exchanged). [RY20, Ch. 1, Definition (computing a function, complexity, rounds)]. Deviation: defined as an `ENat` infimum over protocols, so it is `⊤` when no protocol computes `f`; for finite nonempty `X`, `Y` the value is finite (`UpperBounds.communicationComplexity_le_clog_card`). -/ noncomputable def CommunicationComplexity.Deterministic.communicationComplexity {X Y α : Type*} (f : X → Y → α) : ENat := ⨅ (p : Protocol X Y α) (_ : p.Computes f), (p.complexity : ENat)