AFTD Auto-Formalizing Theoretical Domains

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.
Verified
07 Oct 2026
Axioms
none listed
Built on 3
Used by 18

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)
See it in the graphDiscuss this resultChallenge it