CommunicationComplexity.Deterministic.le_communicationComplexity_of_forall_lt_ncard
theoremverifiedimported Lean
Rectangle-partition lower bound on communication complexity. Let $g : X \to Y \to \alpha$ be a two-argument function and let $n$ be a natural number. If every monochromatic rectangle partition of $g$ consists of strictly more than $2^n$ parts, then the deterministic communication complexity of $g$ satisfies $n + 1 \le D(g)$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in theorem CommunicationComplexity.Deterministic.le_communicationComplexity_of_forall_lt_ncard (g : X → Y → α) (n : ℕ) (h : ∀ Part : Set (Set (X × Y)), Rectangle.IsMonoPartition Part g → 2 ^ n < Set.ncard Part) : (n + 1 : ℕ) ≤ communicationComplexity g
- Source
- TCSlib, `CommunicationComplexity.Deterministic.le_communicationComplexity_of_forall_lt_ncard`
- 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.le_communicationComplexity_of_forall_lt_ncard← CommunicationComplexity.Deterministic.le_communicationComplexity_of_forall_lt_ncard (TCSlib/CommunicationComplexity/DeterministicCC/DetRectangle.lean:509): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- CommunicationComplexity.Deterministic.communicationComplexity_le_iffThreshold characterization of deterministic communication complexity. Let $f : X \to Y \to \alpha$ be a two-argument function and let $n$…
- CommunicationComplexity.Deterministic.le_communicationComplexity_iffLower-bound characterization of communication complexity. Let $f : X \to Y \to \alpha$ be a two-argument function, let…
- CommunicationComplexity.Deterministic.Protocol.complexityThe communication complexity of a protocol $p$ is the worst-case total number of bits exchanged: an output node costs $0$, while an alice…
- CommunicationComplexity.Rectangle.IsMonoPartitionA collection $\mathcal{P}$ of subsets of $X \times Y$ is a monochromatic rectangle partition for $g : X \to Y \to \alpha$ if every…
- CommunicationComplexity.Deterministic.communicationComplexityThe deterministic communication complexity of $f : X \to Y \to \alpha$ is defined as…
- CommunicationComplexity.Deterministic.mono_partition_of_communicationComplexity_leLow deterministic complexity yields a small monochromatic partition. Let $g : X \times Y \to \alpha$ be a two-argument function, and let…
- CommunicationComplexity.Deterministic.ProtocolA deterministic two-party communication protocol over input types $X$ (Alice) and $Y$ (Bob) producing a value of type $\alpha$ is an…
- CommunicationComplexity.Deterministic.Protocol.ComputesA protocol $p$ computes a two-argument function $f : X \to Y \to \alpha$ if $p.\texttt{run}\,x\,y = f\,x\,y$ for all inputs $x : X$…
- Used by 2
- CommunicationComplexity.Functions.Equality.le_communicationComplexityDeterministic complexity lower bound for equality. For every natural number $n \ge 1$, the deterministic communication complexity of the…
- CommunicationComplexity.Functions.Disjointness.le_communicationComplexityLower bound on the communication complexity of disjointness. Fix an integer $n \ge 1$, and consider the set-disjointness function on…
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/-- Rectangle lower-bound method: if every monochromatic rectangle partition of `X × Y` for `g` has more than `2 ^ n` parts, then the deterministic communication complexity of `g` is at least `n + 1` [RY20, Thm 1.7] (contrapositive) / [Rou16, Thm 4.3]. Deviation: stated with `2 ^ n` parts and conclusion `n + 1 ≤ D(g)` rather than `log₂ t ≤ D(g)` for a partition size `t`, avoiding logarithms of naturals. -/theorem CommunicationComplexity.Deterministic.le_communicationComplexity_of_forall_lt_ncard (g : X → Y → α) (n : ℕ) (h : ∀ Part : Set (Set (X × Y)), Rectangle.IsMonoPartition Part g → 2 ^ n < Set.ncard Part) : (n + 1 : ℕ) ≤ communicationComplexity g := by rw [le_communicationComplexity_iff] intro p hp have hle : communicationComplexity g ≤ p.complexity := (communicationComplexity_le_iff g p.complexity).mpr ⟨p, hp, le_refl _⟩ obtain ⟨Part, hPart, hCard⟩ := mono_partition_of_communicationComplexity_le g p.complexity hle have hsuff := h Part hPart by_contra hlt; push_neg at hlt have : 2 ^ p.complexity ≤ 2 ^ n := Nat.pow_le_pow_right (by omega) (by omega) omega