CommunicationComplexity.Deterministic.Protocol.leafRectanglesAux
defimported Lean
For a protocol $p$ and sets $A \subseteq X$, $B \subseteq Y$, $\texttt{leafRectanglesAux}(p, A, B)$ is the collection of rectangles induced by the leaves of $p$ when the reachable inputs are constrained to $A \times B$. It is defined by structural recursion: an output node yields $\{A \times B\}$, while Alice (resp.\ Bob) nodes split $A$ (resp.\ $B$) according to the branching function and recurse.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in def CommunicationComplexity.Deterministic.Protocol.leafRectanglesAux (p : Protocol X Y α) (A : Set X) (B : Set Y) : Set (Set (X × Y))
- Defined in
- TCSlib, `CommunicationComplexity.Deterministic.Protocol.leafRectanglesAux`
- 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.leafRectanglesAux← CommunicationComplexity.Deterministic.Protocol.leafRectanglesAux (TCSlib/CommunicationComplexity/DeterministicCC/DetRectangle.lean:110): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 1
- CommunicationComplexity.Deterministic.ProtocolA deterministic two-party communication protocol over input types $X$ (Alice) and $Y$ (Bob) producing a value of type $\alpha$ is an…
- Used by 12
- CommunicationComplexity.Deterministic.Protocol.aux_finiteFiniteness of the auxiliary leaf rectangles. Let $X$, $Y$, and $\alpha$ be types, let $p$ be a deterministic two-party communication…
- 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.aux_disjointDistinct auxiliary leaf rectangles are disjoint. Let $p$ be a deterministic communication protocol over input types $X$ (Alice) and $Y$…
- CommunicationComplexity.Deterministic.Protocol.aux_monoLeaf rectangles are output-monochromatic. Let $p$ be a deterministic communication protocol over input types $X$ (Alice) and $Y$ (Bob)…
- CommunicationComplexity.Deterministic.Protocol.aux_alice_bitAlice's bit is fixed on a child's leaf rectangle. Let $p$ be a protocol on $X \times Y$, let $A \subseteq X$, $B \subseteq Y$, let…
- CommunicationComplexity.Deterministic.Protocol.aux_cardLeaf rectangle count bounded by two to the complexity. Let $p$ be a deterministic two-party communication protocol with input types $X$…
- CommunicationComplexity.Deterministic.Protocol.aux_disjoint_alice_of_neLeaf rectangles on opposite Alice branches are disjoint. Let $p, q$ be protocols on $X \times Y$, let $A \subseteq X$, $B \subseteq Y$,…
- CommunicationComplexity.Deterministic.Protocol.leafRectanglesThe leaf rectangles of a protocol $p : \texttt{Protocol}\,X\,Y\,\alpha$ form the collection…
- CommunicationComplexity.Deterministic.Protocol.aux_subsetAuxiliary leaf rectangles lie within the constraint. Let $p$ be a deterministic two-party communication protocol over input types $X$…
- CommunicationComplexity.Deterministic.Protocol.aux_coverLeaf rectangles cover the input rectangle. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from a…
- CommunicationComplexity.Deterministic.Protocol.aux_bob_bitBob's bit is fixed on a child's leaf rectangle. Let $p$ be a protocol on $X \times Y$, let $A \subseteq X$, $B \subseteq Y$, let…
- CommunicationComplexity.Deterministic.Protocol.aux_disjoint_bob_of_neLeaf rectangles on opposite Bob branches are disjoint. Let $p, q$ be protocols on $X \times Y$, let $A \subseteq X$, $B \subseteq Y$, let…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in /-- The leaf rectangles of a protocol relative to a constraint rectangle `A ×ˢ B`, i.e. the sets of inputs in `A ×ˢ B` reaching each leaf: a terminal protocol contributes `A ×ˢ B` itself, an Alice node with message function `f` the leaf rectangles of the child reached on bit `b` relative to `(A ∩ {x | f x = b}) ×ˢ B` for both `b`, and a Bob node likewise with the constraint on `B`. `leafRectangles` is the case `A = B = univ`. -/ def CommunicationComplexity.Deterministic.Protocol.leafRectanglesAux (p : Protocol X Y α) (A : Set X) (B : Set Y) : Set (Set (X × Y)) := match p with | output _ => {A ×ˢ B} | alice f P => leafRectanglesAux (P false) (A ∩ {x | f x = false}) B ∪ leafRectanglesAux (P true) (A ∩ {x | f x = true}) B | bob f P => leafRectanglesAux (P false) A (B ∩ {y | f y = false}) ∪ leafRectanglesAux (P true) A (B ∩ {y | f y = true})