CommunicationComplexity.Deterministic.Protocol.distributionalError
defimported Lean
Given a deterministic protocol $p : \mathrm{Protocol}\,X\,Y\,\alpha$, a finite probability space $\mu$ on $X \times Y$, and a target function $f : X \to Y \to \alpha$, the distributional error $p.\mathrm{distributionalError}(\mu, f) \in \mathbb{R}$ is the $\mu$-probability that the output of $p$ disagrees with $f$, i.e.\ $\mu\bigl(\{(x,y) \mid p.\mathrm{run}(x,y) \ne f(x,y)\}\bigr)$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in variable {X Y α : Type*} in noncomputable def CommunicationComplexity.Deterministic.Protocol.distributionalError (p : Protocol X Y α) (μ : FiniteProbabilitySpace (X × Y)) (f : X → Y → α) : ℝ
- Defined in
- TCSlib, `CommunicationComplexity.Deterministic.Protocol.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.distributionalError← CommunicationComplexity.Deterministic.Protocol.distributionalError (TCSlib/CommunicationComplexity/NewmanTheorem/Minimax.lean:61): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 3
- 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.runGiven a protocol $p$,
runevaluates $p$ on inputs $x : X$ and $y : Y$ by recursively following the bit-branching structure until… - CommunicationComplexity.FiniteProbabilitySpaceA typeclass bundling a
MeasureSpacestructure on $\Omega$ together with aCommunicationComplexity.FiniteMeasureSpace…
- Used by 3
- CommunicationComplexity.Deterministic.Protocol.signedBias_eq_one_sub_two_distributionalErrorSigned correlation and distributional error. Let $X$ and $Y$ be the input types of Alice and Bob, and let $\mu$ be a finite probability…
- 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…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in variable {X Y α : Type*} in /-- The distributional error of a deterministic protocol with respect to a distribution `μ` on `X × Y`: the probability, for an input `(x, y)` drawn from `μ`, that the protocol's output disagrees with `f x y`. [RY20, Ch. 3, §Variants of Randomized Protocols: average-case error e w.r.t. µ]. -/ noncomputable def CommunicationComplexity.Deterministic.Protocol.distributionalError (p : Protocol X Y α) (μ : FiniteProbabilitySpace (X × Y)) (f : X → Y → α) : ℝ := by letI := μ exact volume.real {xy : X × Y | p.run xy.1 xy.2 ≠ f xy.1 xy.2}