AFTD Auto-Formalizing Theoretical Domains

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.
Verified
07 Oct 2026
Axioms
none listed
Built on 1
Used by 12

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})
See it in the graphDiscuss this resultChallenge it