AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.communicationComplexity_le_clog_card_X_alpha

theoremverifiedimported Lean

Trivial upper bound on deterministic communication complexity. Let $X$ and $\alpha$ be finite nonempty types, let $Y$ be an arbitrary type, and let $f : X \to Y \to \alpha$ be a two-argument function. Then the deterministic communication complexity of $f$ satisfies \[ D(f) \;\le\; \lceil \log_2 \abs{X} \rceil + \lceil \log_2 \abs{\alpha} \rceil, \] where $\abs{X}$ and $\abs{\alpha}$ denote the cardinalities of $X$ and $\alpha$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
theorem CommunicationComplexity.Deterministic.communicationComplexity_le_clog_card_X_alpha
    {X Y α : Type} [Finite X] [Finite α] [Nonempty X] [Nonempty α]
    (f : X → Y → α) :
    communicationComplexity f ≤
      Nat.clog 2 (Nat.card X) + Nat.clog 2 (Nat.card α)
Source
TCSlib, `CommunicationComplexity.Deterministic.communicationComplexity_le_clog_card_X_alpha`
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 6
Used by 2

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false in/-- The deterministic communication complexity of `f` is at most `⌈log₂ |X|⌉ + ⌈log₂ |α|⌉`, achieved by Alice sending her input, then Bob computing and sending the output [RY20, Ch. 1, §Equality: 'Alice sending her input yields an (n+1)-bit protocol'], [Rou16, §1.7]. Deviation: [RY20] only states the trivial protocol for specific functions (equality, disjointness); here it is stated for an arbitrary function with finite `X` and `α`. -/theorem CommunicationComplexity.Deterministic.communicationComplexity_le_clog_card_X_alpha    {X Y α : Type} [Finite X] [Finite α] [Nonempty X] [Nonempty α]    (f : X → Y → α) :    communicationComplexity f ≤      Nat.clog 2 (Nat.card X) + Nat.clog 2 (Nat.card α) := by  haveI := Fintype.ofFinite X; haveI := Fintype.ofFinite α  exact communicationComplexity_le_of_finiteMessage_protocol    (FiniteMessage.Protocol.alice id fun x =>      FiniteMessage.Protocol.bob (f x) fun a =>        FiniteMessage.Protocol.output a)    -- Step 1: the protocol computes `f`    (by ext x y; unfold FiniteMessage.Protocol.run; rfl)    -- Step 2: its complexity is the claimed bound    (by simp [FiniteMessage.Protocol.complexity, Nat.card_eq_fintype_card, Finset.sup_const])
See it in the graphDiscuss this resultChallenge it