CommunicationComplexity.Deterministic.Protocol.logb_le_complexity_of_distributionalError
Discrepancy lower bound on communication complexity. Let $\mu$ be a finite probability space on $X \times Y$, let $g : X \times Y \to \mathrm{Bool}$ be a Boolean function, and let $\gamma > 0$ be a real number such that every combinatorial rectangle $R \subseteq X \times Y$ satisfies $\abs{\mathrm{disc}_\mu(g, R)} \le \gamma$, where $\mathrm{disc}_\mu(g, R) = \E_{(x,y)\sim\mu}[\mathbf{1}_R(x,y)\,\sigma(g(x,y))]$ and $\sigma(\mathrm{false}) = 1$, $\sigma(\mathrm{true}) = -1$. Let $p$ be a deterministic communication protocol with Boolean outputs, and let $\varepsilon = \mu(\{(x,y) : p(x,y) \ne g(x,y)\})$ be its distributional error in computing $g$ under $\mu$. If $1 - 2\varepsilon > 0$, then the communication complexity of $p$ satisfies \[ \log_2\!\left(\frac{1 - 2\varepsilon}{\gamma}\right) \;\le\; \mathrm{complexity}(p). \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open scoped BigOperators in variable {X Y : Type*} in theorem CommunicationComplexity.Deterministic.Protocol.logb_le_complexity_of_distributionalError [μ : FiniteProbabilitySpace (X × Y)] (g : X → Y → Bool) (γ : ℝ) (p : Protocol X Y Bool) (hdisc : ∀ R : Set (X × Y), Rectangle.IsRectangle R → |discrepancy g R| ≤ γ) (hγ : 0 < γ) (herr : 0 < 1 - 2 * p.distributionalError μ g) : Real.logb 2 ((1 - 2 * p.distributionalError μ g) / γ) ≤ p.complexity
- Formalizes
- Discrepancy lower bound on communication complexity, as formalized in TCSlib (`CommunicationComplexity.Deterministic.Protocol.logb_le_complexity_of_distributionalError`)
- 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.Protocol.logb_le_complexity_of_distributionalError← CommunicationComplexity.Deterministic.Protocol.logb_le_complexity_of_distributionalError (TCSlib/CommunicationComplexity/NewmanTheorem/Discrepancy.lean:384): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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.discrepancyLet $\mu$ be a finite probability space on $X \times Y$, let $g : X \to Y \to \mathrm{Bool}$, and let $S \subseteq X \times Y$. The…
- CommunicationComplexity.Deterministic.Protocol.one_sub_two_distributionalError_le_two_pow_mulDiscrepancy lower bound on distributional error. Let $\mu$ be a finite probability measure on $X \times Y$, 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.distributionalErrorGiven a deterministic protocol $p : \mathrm{Protocol}\,X\,Y\,\alpha$, a finite probability space $\mu$ on $X \times Y$, and a target…
- CommunicationComplexity.Rectangle.IsRectangleA subset $S \subseteq X \times Y$ is a rectangle if it factors as a product $A \times B$ for some $A \subseteq X$ and…
- CommunicationComplexity.FiniteProbabilitySpaceA typeclass bundling a
MeasureSpacestructure on $\Omega$ together with aCommunicationComplexity.FiniteMeasureSpace…
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 MeasureTheory inopen scoped BigOperators invariable {X Y : Type*} in/-- Discrepancy bound in logarithmic form: if every rectangle has absolute discrepancy at most `γ > 0` and a deterministic Boolean protocol `p` has distributional error `e` with `1 − 2e > 0`, then `log₂((1 − 2e) / γ) ≤ complexity of p`. [RY20, Thm 5.2] (distributional form: `log₂((1−2e)/γ) ≤ c`). Follows from `one_sub_two_distributionalError_le_two_pow_mul` by dividing by `γ` and taking logarithms. -/theorem CommunicationComplexity.Deterministic.Protocol.logb_le_complexity_of_distributionalError [μ : FiniteProbabilitySpace (X × Y)] (g : X → Y → Bool) (γ : ℝ) (p : Protocol X Y Bool) (hdisc : ∀ R : Set (X × Y), Rectangle.IsRectangle R → |discrepancy g R| ≤ γ) (hγ : 0 < γ) (herr : 0 < 1 - 2 * p.distributionalError μ g) : Real.logb 2 ((1 - 2 * p.distributionalError μ g) / γ) ≤ p.complexity := by have hmain := one_sub_two_distributionalError_le_two_pow_mul (μ := μ) g γ p hdisc have hdiv : (1 - 2 * p.distributionalError μ g) / γ ≤ (2 : ℝ) ^ p.complexity := by rw [div_le_iff₀ hγ] exact hmain have hpos : 0 < (1 - 2 * p.distributionalError μ g) / γ := by positivity rw [Real.logb_le_iff_le_rpow (b := (2 : ℝ)) (hb := by norm_num) hpos] simpa [Real.rpow_natCast] using hdiv