CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run
theoremverifiedimported Lean
Evaluation of the complete Alice-query tree. Fix a depth $d \in \bbn$, a family of binary query functions $\mathrm{query}_i : X \to \mathrm{Bool}$ for $i \in \mathrm{Fin}\,d$, and a family of deterministic protocols $Q(b)$ indexed by bit patterns $b : \mathrm{Fin}\,d \to \mathrm{Bool}$. Then for every pair of inputs $x : X$ and $y : Y$, the protocol that first has Alice read the $d$ query bits in sequence and then runs $Q$ on the collected pattern evaluates on $(x,y)$ to the same value as the single protocol $Q\bigl(i \mapsto \mathrm{query}_i(x)\bigr)$ evaluated on $(x,y)$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in theorem CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run (d : ℕ) (query : Fin d → X → Bool) (Q : (Fin d → Bool) → Deterministic.Protocol X Y α) (x : X) (y : Y) : (completeTreeAlice d query Q).run x y = (Q (fun i => query i x)).run x y
- Source
- TCSlib, `CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run`
- 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_run← CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run (TCSlib/CommunicationComplexity/DeterministicCC/FiniteMessage.lean:121): adapted
What was changed in
CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run--- TCSlib/CommunicationComplexity/DeterministicCC/FiniteMessage.lean:121 (CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run) +++ as compiled here @@ -1,4 +1,5 @@ -/-- Running the complete tree of depth `d` on `(x, y)` is the same as running the -continuation `Q` at the bit vector `i ↦ query i x` on `(x, y)`. -/ -private theorem completeTreeAlice_run (d : ℕ) (query : Fin d → X → Bool) +set_option relaxedAutoImplicit false in +set_option autoImplicit false in +variable {X Y α : Type*} in +theorem CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run (d : ℕ) (query : Fin d → X → Bool) (Q : (Fin d → Bool) → Deterministic.Protocol X Y α) (x : X) (y : Y) : @@ -17,3 +18,3 @@ fun i => query i x := by - simpa [Function.comp] using (Fin.cons_self_tail (fun i => query i x)) + exact Fin.cons_self_tail (fun i => query i x) rw [this] - Verified
- 07 Oct 2026
- Axioms
Quot.soundpropext- Built on 4
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAliceAn auxiliary construction: given $d$ binary query functions $\mathrm{query}_i : X \to \mathrm{Bool}$ and a family of binary protocols…
- CommunicationComplexity.Deterministic.ProtocolA deterministic two-party communication protocol over input types $X$ (Alice) and $Y$ (Bob) producing a value of type $\alpha$ is an…
- CommunicationComplexity.Deterministic.Protocol.runGiven a protocol $p$,
runevaluates $p$ on inputs $x : X$ and $y : Y$ by recursively following the bit-branching structure until… - CommunicationComplexity.Deterministic.Protocol.aux_monoLeaf rectangles are output-monochromatic. Let $p$ be a deterministic communication protocol over input types $X$ (Alice) and $Y$ (Bob)…
- Used by 1
- 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…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {X Y α : Type*} in/-- Running the complete tree of depth `d` on `(x, y)` is the same as running the continuation `Q` at the bit vector `i ↦ query i x` on `(x, y)`. -/theorem CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run (d : ℕ) (query : Fin d → X → Bool) (Q : (Fin d → Bool) → Deterministic.Protocol X Y α) (x : X) (y : Y) : (completeTreeAlice d query Q).run x y = (Q (fun i => query i x)).run x y := by induction d with | zero => simp only [completeTreeAlice] congr; ext i; exact i.elim0 | succ d ih => simp only [completeTreeAlice, Deterministic.Protocol.run] rw [ih] -- Goal: (Q (Fin.cons (query 0 x) ...)).run x y = (Q (fun i => query i x)).run x y -- Suffices to show the arguments to Q are equal have : Fin.cons (query 0 x) (fun i => (query ∘ Fin.succ) i x) = fun i => query i x := by exact Fin.cons_self_tail (fun i => query i x) rw [this]