CommunicationComplexity.Rectangle.IsRectangle
defimported Lean
A subset $S \subseteq X \times Y$ is a rectangle if it factors as a product $A \times B$ for some $A \subseteq X$ and $B \subseteq Y$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in def CommunicationComplexity.Rectangle.IsRectangle (S : Set (X × Y)) : Prop
- Defined in
- TCSlib, `CommunicationComplexity.Rectangle.IsRectangle`
- 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.Rectangle.IsRectangle← CommunicationComplexity.Rectangle.IsRectangle (TCSlib/CommunicationComplexity/DeterministicCC/Rectangle.lean:62): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 13
- CommunicationComplexity.Deterministic.Protocol.aux_isRectangleAuxiliary leaf sets are rectangles. Let $p$ be a deterministic two-party communication protocol over input types $X$ (Alice) and $Y$…
- CommunicationComplexity.Deterministic.Protocol.leafRectangles_isMonoPartitionLeaf rectangles of a protocol form a monochromatic partition. Let $p$ be a deterministic two-party communication protocol over input types…
- is_monochromatic_coverGiven types $X$ and $Y$, a curried Boolean function $f : X \to Y \to \mathrm{Bool}$, and a Boolean value $b : \mathrm{Bool}$, a collection…
- 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.Rectangle.IsMonoPartitionA collection $\mathcal{P}$ of subsets of $X \times Y$ is a monochromatic rectangle partition for $g : X \to Y \to \alpha$ if every…
- 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…
- is_monochromatic_cover_allGiven types $X$ and $Y$ and a curried Boolean function $f : X \to Y \to \mathrm{Bool}$, a collection…
- CommunicationComplexity.Deterministic.Rank.rank_rectMatrix_le_oneCombinatorial rectangles have rank-one indicator matrices. Let $X$ be any set and $Y$ a finite set, and let $R \subseteq X \times Y$ be a…
- CommunicationComplexity.Rectangle.IsFoolingSetA set $S \subseteq X \times Y$ is a fooling set for $g : X \to Y \to \alpha$ if every monochromatic rectangle with respect to $g$…
- CommunicationComplexity.Rectangle.IsRectangle_iffCross characterization of combinatorial rectangles. A subset $R \subseteq X \times Y$ is a rectangle — that is, $R = A \times B$ for some…
- rectangle_size_boundFor finite types $X$ and $Y$ and a curried Boolean function $f : X \to Y \to \mathrm{Bool}$, the prior-free rectangle-size bound…
- CommunicationComplexity.Deterministic.Protocol.leafRectangles_isRectangleLeaf rectangles are combinatorial rectangles. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in /-- A subset of `X × Y` is a (combinatorial) rectangle if it is a product `A ×ˢ B` of a set of `X`-inputs and a set of `Y`-inputs. [RY20, Ch. 1, 'Rectangles'] / [Rou16, §4.2.4 Definition (rectangle)]. -/ def CommunicationComplexity.Rectangle.IsRectangle (S : Set (X × Y)) : Prop := ∃ A : Set X, ∃ B : Set Y, S = A ×ˢ B