AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice

defimported Lean

An auxiliary construction: given $d$ binary query functions $\mathrm{query}_i : X \to \mathrm{Bool}$ and a family of binary protocols $Q : (\mathrm{Fin}\,d \to \mathrm{Bool}) \to \mathrm{Protocol}\,X\,Y\,\alpha$, builds a single binary protocol that reads each query bit from Alice in sequence and then runs $Q$ on the collected bit pattern.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
def CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice (d : ℕ) (query : Fin d → X → Bool)
    (Q : (Fin d → Bool) → Deterministic.Protocol X Y α) : Deterministic.Protocol X Y α
Defined in
TCSlib, `CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice`
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 6

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
/-- The complete binary protocol tree of depth `d` in which Alice sends the `d` bits `query 0 x, …, query (d-1) x` in order and the protocol then continues as `Q bits`, where `bits` is the vector of bits sent. -/
def CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice (d : ℕ) (query : Fin d → X → Bool)
    (Q : (Fin d → Bool) → Deterministic.Protocol X Y α) : Deterministic.Protocol X Y α :=
  match d with
  | 0 => Q Fin.elim0
  | d + 1 => Deterministic.Protocol.alice (query 0) (fun b =>
      completeTreeAlice d (query ∘ Fin.succ) (fun bits => Q (Fin.cons b bits)))
See it in the graphDiscuss this resultChallenge it