CommunicationComplexity.FiniteProbabilitySpace
classimported Lean
A typeclass bundling a MeasureSpace structure on $\Omega$ together with a
CommunicationComplexity.FiniteMeasureSpace witness and an IsProbabilityMeasure instance for the
canonical volume measure. This makes $\Omega$ simultaneously a finite discrete
measurable space and a probability space.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open scoped ProbabilityTheory in class CommunicationComplexity.FiniteProbabilitySpace (Ω : Type*)
- Defined in
- TCSlib, `CommunicationComplexity.FiniteProbabilitySpace`
- 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.FiniteProbabilitySpace← CommunicationComplexity.FiniteProbabilitySpace (TCSlib/CommunicationComplexity/NewmanTheorem/FiniteProbabilitySpace.lean:86): verbatimattribute [instance] CommunicationComplexity.FiniteProbabilitySpace.toMeasureSpace← attribute [instance] CommunicationComplexity.FiniteProbabilitySpace.toMeasureSpace (TCSlib/CommunicationComplexity/NewmanTheorem/FiniteProbabilitySpace.lean:94): verbatimattribute [instance] CommunicationComplexity.FiniteProbabilitySpace.finite← attribute [instance] CommunicationComplexity.FiniteProbabilitySpace.finite (TCSlib/CommunicationComplexity/NewmanTheorem/FiniteProbabilitySpace.lean:95): verbatimattribute [instance] CommunicationComplexity.FiniteProbabilitySpace.prob← attribute [instance] CommunicationComplexity.FiniteProbabilitySpace.prob (TCSlib/CommunicationComplexity/NewmanTheorem/FiniteProbabilitySpace.lean:96): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 1
- CommunicationComplexity.FiniteMeasureSpaceA typeclass for a measurable space $\Omega$ that is simultaneously finite (carries a
Fintypeinstance) and discrete (every subset…
- CommunicationComplexity.FiniteMeasureSpaceA typeclass for a measurable space $\Omega$ that is simultaneously finite (carries a
- Used by 35
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocolGiven a public-coin finite-message protocol $p$ over a probability space $\Omega$ that $\varepsilon$-computes $f : X \to Y \to \alpha$,…
- CommunicationComplexity.PrivateCoin.communicationComplexity_le_of_finiteMessageFinite-probability protocols bound private-coin complexity. Let $X$, $Y$, and $\alpha$ be types, let $f : X \to Y \to \alpha$ be the…
- 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.FiniteProbabilitySpace.measureReal_prodProduct measure of a rectangle. Let $\Omega_1$ and $\Omega_2$ be finite probability spaces, with respective probability measures $\bbP_1$…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.exists_good_randomnessExistence of good randomness for derandomization. Let $\Omega$ be a finite probability space and let $X$ and $Y$ be finite input sets. Let…
- CommunicationComplexity.Deterministic.Protocol.mem_leafRectanglesFinsetMembership in the finite set of leaf rectangles. Let $X \times Y$ carry the structure of a finite probability space, let $p$ be a…
- CommunicationComplexity.instProdCommunicationComplexity.instProd
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.toCoinTape_complexityCoin-tape conversion preserves complexity. Let $\Omega$ be a finite probability space, and let $p$ be a public-coin finite-message…
- CommunicationComplexity.FiniteProbabilitySpace.integral_comp_evalMarginal of a coordinate integral over a product space. Let $\iota$ be a finite index type and let $\Omega$ be a finite probability space,…
- 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.coinTapeFiniteProbabilitySpaceCommunicationComplexity.coinTapeFiniteProbabilitySpace
- 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.Internal.product_coin_approxProduct-space coin approximation. Let $\Omega_X$ and $\Omega_Y$ be finite probability spaces, and let $\delta > 0$. Give each coin-tape…
- 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.sum_indicator_leafRectangles_eqIndicator sum over leaf rectangles recovers the protocol output. Let $X$ and $Y$ be input types whose product $X \times Y$ carries a…
- 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.FiniteProbabilitySpace.measureReal_iUnion_fintypeFinite additivity of the probability measure. Let $\Omega$ be a finite probability space and let $\iota$ be a finite index set. If…
- CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.toCoinTapeGiven a finite-message private-coin protocol $p$ over finite probability spaces $\Omega_X$ and $\Omega_Y$, and a tolerance $\delta > 0$,…
- 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…
- CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.toCoinTape_approxSatisfiesCoin-tape conversion preserves approximate correctness. Let $p$ be a private-coin finite-message protocol over input types $X$, $Y$ and…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol_ApproxComputesNewman's reduction preserves approximate correctness. Let $\Omega$ be a finite probability space, let $X$ and $Y$ be finite types, and let…
- CommunicationComplexity.Deterministic.Protocol.leafRectanglesFinsetGiven a finite probability space $\mu$ on $X \times Y$ and a deterministic protocol $p$, this is the canonical
Finsetenumerating… - 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.FiniteProbabilitySpace.ofGiven a type $\Omega$ already equipped with a
MeasureSpace,Fintype,DiscreteMeasurableSpace, and… - CommunicationComplexity.FiniteProbabilitySpace.measureReal_eq_integral_indicator_oneMeasure of a set as the integral of its indicator. Let $\Omega$ be a finite probability space and let $S \subseteq \Omega$. Then the…
- CommunicationComplexity.FiniteProbabilitySpace.measureReal_finsetAdditivity of the measure over a finite set. Let $\Omega$ be a finite probability space, and let $T$ be a finite subset of $\Omega$.…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol_complexityCommunication cost of the Newman protocol. Let $X$ and $Y$ be finite types, let $\Omega$ be a finite probability space, and let $p$ be a…
- CommunicationComplexity.Unit.finiteProbabilitySpaceCommunicationComplexity.Unit.finiteProbabilitySpace
- CommunicationComplexity.FiniteProbabilitySpace.measureReal_preimage_finsetMeasure of a preimage of a finite set. Let $\Xi$ be a finite probability space and let $\Omega$ be a measurable space in which every…
- CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.toCoinTape_complexityCoin-tape conversion preserves communication complexity. Let $\Omega_X$ and $\Omega_Y$ be finite probability spaces, let $X$, $Y$ be input…
- CommunicationComplexity.instPiCommunicationComplexity.instPi
- CommunicationComplexity.FiniteProbabilitySpace.hasSum_measure_singletonsSingleton masses of a finite probability space sum to one. Let $\Omega$ be a finite probability space, so that $\Omega$ is finite and…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.toCoinTapeGiven a public-coin finite-message protocol $p$ over an arbitrary finite probability space $\Omega$ and a slack $\delta > 0$, this…
- CommunicationComplexity.PublicCoin.newmanIndexSpace.finiteProbabilitySpaceCommunicationComplexity.PublicCoin.newmanIndexSpace.finiteProbabilitySpace
- CommunicationComplexity.Internal.single_coin_approxApproximating a finite probability space by fair coin flips. Let $\Omega$ be a finite probability space, and let $\delta > 0$. Then there…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open scoped ProbabilityTheory in /-- A finite probability space: a type `Ω` equipped with a measure space structure whose measurable structure is discrete, whose underlying type is finite, and whose `volume` is a probability measure. This is the ambient structure for the randomness of public-coin and private-coin protocols. -/ class CommunicationComplexity.FiniteProbabilitySpace (Ω : Type*) where toMeasureSpace : MeasureSpace Ω finite : @FiniteMeasureSpace Ω toMeasureSpace.toMeasurableSpace prob : @IsProbabilityMeasure Ω toMeasureSpace.toMeasurableSpace toMeasureSpace.volume attribute [instance] CommunicationComplexity.FiniteProbabilitySpace.toMeasureSpace attribute [instance] CommunicationComplexity.FiniteProbabilitySpace.finite attribute [instance] CommunicationComplexity.FiniteProbabilitySpace.prob