CommunicationComplexity.discrepancy
defimported Lean
Let $\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 discrepancy of $g$ on $S$
with respect to $\mu$ is
\[
\mathrm{disc}_\mu(g, S)
\;=\;
\mathbb{E}_{(x,y)\sim\mu}\bigl[\mathbf{1}_{S}(x,y)\cdot\sigma(g(x,y))\bigr],
\]
where $\sigma : \mathrm{Bool} \to \{-1,1\}$ is the sign map CommunicationComplexity.boolSign.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open scoped BigOperators in variable {X Y : Type*} in noncomputable def CommunicationComplexity.discrepancy [μ : FiniteProbabilitySpace (X × Y)] (g : X → Y → Bool) (S : Set (X × Y)) : ℝ
- Defined in
- TCSlib, `CommunicationComplexity.discrepancy`
- 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.discrepancy← CommunicationComplexity.discrepancy (TCSlib/CommunicationComplexity/NewmanTheorem/Discrepancy.lean:65): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 2
- CommunicationComplexity.boolSign$\texttt{boolSign} : \mathrm{Bool} \to \mathbb{R}$ assigns the real value $1$ to $\mathrm{false}$ and $-1$ to $\mathrm{true}$, embedding…
- CommunicationComplexity.FiniteProbabilitySpaceA typeclass bundling a
MeasureSpacestructure on $\Omega$ together with aCommunicationComplexity.FiniteMeasureSpace…
- Used by 4
- CommunicationComplexity.Deterministic.Protocol.signedBias_eq_sum_rectanglesSigned bias as a sum over leaf rectangles. Let $\mu$ be a finite probability space on $X \times Y$, let $p$ be a deterministic Boolean…
- CommunicationComplexity.Deterministic.Protocol.logb_le_complexity_of_distributionalErrorDiscrepancy lower bound on communication complexity. Let $\mu$ be a finite probability space on $X \times Y$, let…
- 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.Protocol.nonneg_of_discrepancy_boundDiscrepancy bound is nonnegative. Let $X \times Y$ carry a finite probability space $\mu$, let $g : X \to Y \to \mathrm{Bool}$ be a…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open scoped BigOperators in variable {X Y : Type*} in /-- The discrepancy of a Boolean function `g` on a subset `S ⊆ X × Y` with respect to a distribution `μ` on `X × Y`: the expectation under `μ` of the indicator of `S` times the `±1` sign of `g`, i.e. the `μ`-mass of the `false` part of `S` minus the `μ`-mass of its `true` part. [RY20, Ch. 5, Definition (Discrepancy)]. Deviation: taken relative to an arbitrary finite distribution `μ` on `X × Y` (RY20 takes the expectation over "a random input x", uniform in its applications such as Thm 5.6), and defined as the signed expectation, without RY20's absolute value; the sign convention `boolSign` (`false ↦ 1`, `true ↦ −1`) agrees with RY20's `(−1)^{g(x)}`. The lower bounds below use `|discrepancy g R|`. -/ noncomputable def CommunicationComplexity.discrepancy [μ : FiniteProbabilitySpace (X × Y)] (g : X → Y → Bool) (S : Set (X × Y)) : ℝ := by classical exact ∫ xy : X × Y, (if xy ∈ S then (1 : ℝ) else 0) * boolSign (g xy.1 xy.2)