CommunicationComplexity.Deterministic.Protocol.rectangleSign
defimported Lean
For a deterministic Boolean protocol $p$ and a set $R \subseteq X \times Y$, the rectangle sign is $+1$ if the protocol outputs $\mathrm{false}$ on every point of $R$, and $-1$ otherwise.
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.Deterministic.Protocol.rectangleSign (p : Protocol X Y Bool) (R : Set (X × Y)) : ℝ
- Defined in
- TCSlib, `CommunicationComplexity.Deterministic.Protocol.rectangleSign`
- 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.rectangleSign← CommunicationComplexity.Deterministic.Protocol.rectangleSign (TCSlib/CommunicationComplexity/NewmanTheorem/Discrepancy.lean:149): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 2
- 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…
- Used by 5
- 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.rectangleSign_absRectangle sign has absolute value one. Let $p$ be a deterministic Boolean two-party communication protocol on input types $X$ (Alice) and…
- CommunicationComplexity.Deterministic.Protocol.rectangleSign_eq_boolSignRectangle sign equals Boolean sign on leaf rectangles. Let $p$ be a deterministic two-party communication protocol with Boolean output,…
- 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…
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 sign attached to a rectangle in the leaf partition of a Boolean protocol: it is `1` when the protocol outputs `false` on that rectangle, and `-1` otherwise. -/ noncomputable def CommunicationComplexity.Deterministic.Protocol.rectangleSign (p : Protocol X Y Bool) (R : Set (X × Y)) : ℝ := by classical exact if ∀ xy ∈ R, p.run xy.1 xy.2 = false then 1 else -1