CommunicationComplexity.Deterministic.clog_ncard_le_communicationComplexity
theoremverifiedformalizationimported Lean
Fooling-set lower bound for deterministic communication complexity. Let $g : X \times Y \to \alpha$ be a two-argument function and let $S \subseteq X \times Y$ be a fooling set for $g$, meaning that every rectangle that is monochromatic for $g$ meets $S$ in at most one point. Then the deterministic communication complexity of $g$ satisfies \[ \lceil \log_2 \abs{S} \rceil \;\le\; D(g), \] where $\abs{S}$ is the number of elements of $S$ and both sides are compared in $\bbn_\infty$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in theorem CommunicationComplexity.Deterministic.clog_ncard_le_communicationComplexity (g : X → Y → α) (S : Set (X × Y)) (hS : Rectangle.IsFoolingSet S g) : (Nat.clog 2 (Set.ncard S) : ENat) ≤ communicationComplexity g
- Formalizes
- Fooling-set lower bound for deterministic communication complexity, as formalized in TCSlib (`CommunicationComplexity.Deterministic.clog_ncard_le_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.CommunicationComplexity.Deterministic.clog_ncard_le_communicationComplexity← CommunicationComplexity.Deterministic.clog_ncard_le_communicationComplexity (TCSlib/CommunicationComplexity/DeterministicCC/DetRectangle.lean:554): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- CommunicationComplexity.Deterministic.communicationComplexityThe deterministic communication complexity of $f : X \to Y \to \alpha$ is defined as…
- CommunicationComplexity.Deterministic.foolingSet_ncard_le_pow_of_communicationComplexity_leFooling set bound from communication complexity. Let $g : X \times Y \to \alpha$ be a two-argument function, and let…
- CommunicationComplexity.Rectangle.IsFoolingSetA set $S \subseteq X \times Y$ is a fooling set for $g : X \to Y \to \alpha$ if every monochromatic rectangle with respect to $g$…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {X Y α : Type*} in/-- Fooling-set lower bound: the deterministic communication complexity of `g` is at least `⌈log₂ |S|⌉` for every fooling set `S` of `g` [Rou16, Cor 4.7] (also [RY20, Ch. 1, §Using Fooling Sets]). Deviation: the ceiling logarithm is `Nat.clog 2`, and the inequality is in `ℕ∞`, so it holds trivially when the complexity is infinite. -/theorem CommunicationComplexity.Deterministic.clog_ncard_le_communicationComplexity (g : X → Y → α) (S : Set (X × Y)) (hS : Rectangle.IsFoolingSet S g) : (Nat.clog 2 (Set.ncard S) : ENat) ≤ communicationComplexity g := by match h : communicationComplexity g with | ⊤ => exact le_top | (n : ℕ) => exact_mod_cast (Nat.clog_le_iff_le_pow (by norm_num)).mpr (foolingSet_ncard_le_pow_of_communicationComplexity_le g S n hS (le_of_eq h))