AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.OneWay.le_communicationComplexity_iff

theoremverifiedimported Lean

Lower bound characterization of one-way communication complexity. Let $f : X \to Y \to \alpha$ be a function and let $k \in \bbn$. Then $k$ is at most the one-way deterministic communication complexity of $f$ (as an inequality in $\bbn_\infty$) if and only if every one-way deterministic protocol that computes $f$ has bit cost at least $k$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
theorem CommunicationComplexity.Deterministic.OneWay.le_communicationComplexity_iff (f : X → Y → α) (k : ℕ) :
    (k : ENat) ≤ communicationComplexity f ↔
      ∀ p : Protocol X Y α, Protocol.Computes p f → k ≤ Protocol.cost p
Source
TCSlib, `CommunicationComplexity.Deterministic.OneWay.le_communicationComplexity_iff`
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
Classical.choiceQuot.soundpropext
Built on 5
Used by 1

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {X Y α : Type*} in/-- The one-way communication complexity of `f` is at least `k` if and only if every one-way protocol computing `f` has cost at least `k`. -/theorem CommunicationComplexity.Deterministic.OneWay.le_communicationComplexity_iff (f : X → Y → α) (k : ℕ) :    (k : ENat) ≤ communicationComplexity f ↔      ∀ p : Protocol X Y α, Protocol.Computes p f → k ≤ Protocol.cost p := by  simp [communicationComplexity, le_iInf_iff, Nat.cast_le]
See it in the graphDiscuss this resultChallenge it