AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Functions.Disjointness.communicationComplexity_eq

theoremverifiedformalizationimported Lean

Deterministic complexity of set disjointness. Let $n \geq 1$, and let $\mathrm{disjointness}(n, \cdot, \cdot)$ denote the two-party Boolean function that, given subsets $X, Y \subseteq [n]$ held by Alice and Bob respectively, returns $\mathtt{true}$ exactly when $X \cap Y = \emptyset$. Then the deterministic communication complexity of this function is exactly $n + 1$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open CommunicationComplexity.Rectangle in
open scoped symmDiff in
theorem CommunicationComplexity.Functions.Disjointness.communicationComplexity_eq (n : ℕ) (hn : 1 ≤ n) :
    Deterministic.communicationComplexity (disjointness n) = n + 1
Formalizes
Deterministic complexity of set disjointness, as formalized in TCSlib (`CommunicationComplexity.Functions.Disjointness.communicationComplexity_eq`)
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

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen CommunicationComplexity.Rectangle inopen scoped symmDiff in/-- For `n ≥ 1`, the deterministic communication complexity of disjointness on subsets of `[n]` is exactly `n + 1` [RY20, Thm 1.25]. Deviation: [RY20] states the lower bound `≥ n + 1`; combined with the trivial upper bound this gives the exact value ([Rou16, Cor 4.8] only gives `≥ n`). -/theorem CommunicationComplexity.Functions.Disjointness.communicationComplexity_eq (n : ℕ) (hn : 1 ≤ n) :    Deterministic.communicationComplexity (disjointness n) = n + 1 := by  apply le_antisymm (communicationComplexity_le n)  exact le_communicationComplexity n hn
See it in the graphDiscuss this resultChallenge it