CommunicationComplexity.Functions.Disjointness.communicationComplexity_le
theoremverifiedimported Lean
Upper bound on the communication complexity of disjointness. Fix $n \in \bbn$, and let both players' inputs range over subsets of $[n] = \{0, 1, \dots, n-1\}$, so that Alice holds $X \subseteq [n]$ and Bob holds $Y \subseteq [n]$. The deterministic communication complexity of the set-disjointness function, which returns $\mathtt{true}$ exactly when $X \cap Y = \emptyset$, is at most $n + 1$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open scoped symmDiff in theorem CommunicationComplexity.Functions.Disjointness.communicationComplexity_le (n : ℕ) : Deterministic.communicationComplexity (disjointness n) ≤ n + 1
- Source
- TCSlib, `CommunicationComplexity.Functions.Disjointness.communicationComplexity_le`
- 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.Functions.Disjointness.communicationComplexity_le← CommunicationComplexity.Functions.Disjointness.communicationComplexity_le (TCSlib/CommunicationComplexity/DeterministicCC/FuncDisjointness.lean:151): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- CommunicationComplexity.Deterministic.communicationComplexity_le_clog_card_X_alphaTrivial upper bound on deterministic communication complexity. Let $X$ and $\alpha$ be finite nonempty types, let $Y$ be an arbitrary…
- CommunicationComplexity.Functions.Disjointness.disjointnessFor $n \in \mathbb{N}$ and subsets $X, Y \subseteq [n]$, $\mathrm{disjointness}(n, X, Y)$ is the Boolean function that returns…
- CommunicationComplexity.Functions.Disjointness.clog_two_twoCeiling logarithm of two in base two. The ceiling base-$2$ logarithm of $2$ equals $1$: $\lceil \log_2 2 \rceil = 1$, i.e.\…
- CommunicationComplexity.Deterministic.communicationComplexityThe deterministic communication complexity of $f : X \to Y \to \alpha$ is defined as…
- Used by 1
- CommunicationComplexity.Functions.Disjointness.communicationComplexity_eqDeterministic complexity of set disjointness. Let $n \geq 1$, and let $\mathrm{disjointness}(n, \cdot, \cdot)$ denote the two-party…
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 inopen scoped symmDiff in/-- The deterministic communication complexity of disjointness on subsets of `[n]` is at most `n + 1`: Alice sends her set as `n` bits, and Bob sends one bit for the answer [RY20, Ch. 1, §Disjointness: 'Alice sending X gives an (n+1)-bit protocol']. -/theorem CommunicationComplexity.Functions.Disjointness.communicationComplexity_le (n : ℕ) : Deterministic.communicationComplexity (disjointness n) ≤ n + 1 := by calc Deterministic.communicationComplexity (disjointness n) ≤ Nat.clog 2 (Nat.card (Set (Fin n))) + Nat.clog 2 (Nat.card Bool) := Deterministic.communicationComplexity_le_clog_card_X_alpha (disjointness n) _ = n + 1 := by simp only [Nat.card_eq_fintype_card, Fintype.card_set, Fintype.card_fin, Fintype.card_bool, Nat.one_lt_ofNat, Nat.clog_pow] rw [clog_two_two] norm_num