AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.le_communicationComplexity_iff

theoremverifiedimported Lean

Lower-bound characterization of communication complexity. Let $f : X \to Y \to \alpha$ be a two-argument function, let $D(f) \in \bbn_\infty$ denote its deterministic communication complexity, and let $n$ be a natural number. Then $n \le D(f)$ if and only if every deterministic protocol $p$ that computes $f$ has communication complexity at least $n$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
theorem CommunicationComplexity.Deterministic.le_communicationComplexity_iff
    {X Y α : Type*} (f : X → Y → α) (n : ℕ) :
    (n : ENat) ≤ communicationComplexity f ↔
      ∀ p : Protocol X Y α,
        p.Computes f → n ≤ p.complexity
Source
TCSlib, `CommunicationComplexity.Deterministic.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 4
Used by 3

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false in/-- The deterministic communication complexity of `f` is at least `n` if and only if every protocol computing `f` uses at least `n` bits. This is the form in which lower bounds are proved. -/theorem CommunicationComplexity.Deterministic.le_communicationComplexity_iff    {X Y α : Type*} (f : X → Y → α) (n : ℕ) :    (n : ENat) ≤ communicationComplexity f ↔      ∀ p : Protocol X Y α,        p.Computes f → n ≤ p.complexity := by  simp only [communicationComplexity,    le_iInf_iff, Nat.cast_le]
See it in the graphDiscuss this resultChallenge it