Alice-starting exact pointer jumping
OpenQAlgorithms.Papers.Independent.Intakethird100.P81.alice_starting_pointer_upperLet and . Alice and Bob have unrestricted pointer maps on two disjoint sets of labelled vertices, and is a fixed Alice vertex independent of the inputs. Let be the endpoint after pointer applications. There is an absolute , chosen before , and an Alice-starting protocol with at most messages which is correct on every input with probability one and has worst-case bit cost
The output is the whole endpoint, so its bit parity is available locally as well. The last pointer application is local to the receiver after the charged messages; announcing the answer is uncharged. The public-mixture representation includes a deterministic protocol as a single seed.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P81
noncomputable section
open scoped Matrix ComplexConjugate ENNReal
attribute [local instance] Classical.propDecidable
namespace QAlgorithms.Papers.Independent.Intakethird100.P81
open QAlgorithms.Papers.Independent.Information100.P54 (relativeEntropyBits)
open QAlgorithms.Papers.Independent.Bridge50.P44 (ClassicalFirst)
/-- Abstract p.1 and Definition 11 p.12: Alice starts, with exact endpoint output after
k+1 evaluations; the final receiver performs the last evaluation locally. -/
theorem alice_starting_pointer_upper :
∃ C : ℝ, 0 < C ∧ ∀ (k n : ℕ), 0 < k → 2 ≤ n → ∀ v1 : Fin n,
∃ (c : ℕ) (P : PublicProtocol (PointerMap n) (PointerMap n) (Vertex n)),
P.bounded .alice k c ∧ P.computes (endpoint k v1) 0 ∧
(c : ℝ) ≤ C * k * Real.logb 2 n := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P81
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
There exists a real constant such that, for every pair of natural numbers with and , and every starting index , there exist a natural number and a public randomized classical protocol with inputs and output in the disjoint union of two copies of , satisfying the following conditions. The protocol consists of finitely many deterministic communication trees with nonnegative real weights summing to one. Each internal node sends one Boolean determined solely by the sending party’s input and follows the corresponding branch; a leaf outputs a function of either Alice’s input or Bob’s input. Every tree of strictly positive weight has communication cost at most , where cost is the maximum number of internal nodes on a path, and has at most rounds starting with Alice: an output-only tree has zero rounds, while a nonempty path counts its consecutive speaker blocks, with an additional initial round if its first speaker is Bob. For every , the total weight of trees whose output is is at least , where and . Finally, . Trees of weight zero are not subject to the cost and round bounds.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.