AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.communicationComplexity_le_iff

theoremverifiedimported Lean

Threshold characterization of deterministic communication complexity. Let $f : X \to Y \to \alpha$ be a two-argument function and let $n$ be a natural number. Then the deterministic communication complexity $D(f)$ satisfies $D(f) \le n$ if and only if there exists a deterministic communication protocol $p$ over inputs $X$ and $Y$ that computes $f$ and whose communication complexity is at most $n$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
theorem CommunicationComplexity.Deterministic.communicationComplexity_le_iff
    {X Y α : Type*} (f : X → Y → α) (n : ℕ) :
    communicationComplexity f ≤ n ↔
      ∃ p : Protocol X Y α,
        p.Computes f ∧ p.complexity ≤ n
Source
TCSlib, `CommunicationComplexity.Deterministic.communicationComplexity_le_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 6

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false in/-- The deterministic communication complexity of `f` is at most `n` if and only if some protocol computes `f` using at most `n` bits. -/theorem CommunicationComplexity.Deterministic.communicationComplexity_le_iff    {X Y α : Type*} (f : X → Y → α) (n : ℕ) :    communicationComplexity f ≤ n ↔      ∃ p : Protocol X Y α,        p.Computes f ∧ p.complexity ≤ n := by  simp only [communicationComplexity,    Internal.enat_iInf_le_coe_iff, Nat.cast_le, exists_prop]
See it in the graphDiscuss this resultChallenge it