AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.Protocol.leafRectangles_card

theoremverifiedimported Lean

Leaf rectangle count is at most two to the complexity. Let $p$ be a deterministic two-party communication protocol over input types $X$ and $Y$ producing values in $\alpha$, and let $c$ be its communication complexity. Then the number of leaf rectangles of $p$ is at most $2^{c}$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
lemma CommunicationComplexity.Deterministic.Protocol.leafRectangles_card (p : Protocol X Y α) :
    Set.ncard (leafRectangles p) ≤ 2 ^ p.complexity
Source
TCSlib, `CommunicationComplexity.Deterministic.Protocol.leafRectangles_card`
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
Classical.choiceQuot.soundpropext
Built on 4
Used by 3

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
/-- A protocol of communication complexity `c` has at most `2 ^ c` leaf rectangles [RY20, Lemma 1.2] (a protocol tree of depth `c` has at most `2 ^ c` leaves). -/
lemma CommunicationComplexity.Deterministic.Protocol.leafRectangles_card (p : Protocol X Y α) :
    Set.ncard (leafRectangles p) ≤ 2 ^ p.complexity :=
  aux_card p Set.univ Set.univ
See it in the graphDiscuss this resultChallenge it