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.CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice← CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice (TCSlib/CommunicationComplexity/DeterministicCC/FiniteMessage.lean:112): 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 6
- Physlib.MultiIndex.toList_singlePhyslib.MultiIndex.toList_single
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_complexityComplexity of the complete Alice-query tree. Fix a natural number $d$, together with binary query functions…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_runEvaluation of the complete Alice-query tree. Fix a depth $d \in \bbn$, a family of binary query functions…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.encode_aliceBinary encoding of a finite-alphabet message from Alice. Let $X$, $Y$, and $\alpha$ be types, let $\beta$ be a finite nonempty type, let…
- Physlib.MultiIndex.toList_increment_zeroPhyslib.MultiIndex.toList_increment_zero
- Physlib.MultiIndex.length_toListPhyslib.MultiIndex.length_toList
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)))