Persistent call history and exact event counters
ProvedNearlyOptimalPPR.Computation.recursive_call_historyalgorithm-analysisgraph-theorypagerank
Every finite-prefix recursive execution has persistent call information, monotone closed-call records, and fixed parameters throughout the open lifetime of a frame. Its event counters are exact:
The assertions hold for every finite graph, seed, depth, schedule, and real parameters. Information persistence means a recorded call retains its level, scale, and block size. Fixed frame parameters include its threshold and identifier. No positivity, termination, accuracy, or complexity assumption is needed.
These operational bookkeeping facts connect the event counts in the finite-prefix proof of Lemma 4.4 to the actual counters of Algorithms 6–9.
Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_work_analysis import Definitions.Def_NearlyOptimalPPR_Computation_push set_option autoImplicit false open Finset Matrix NearlyOptimalPPR.Computation attribute [local instance] Classical.propDecidable
Formal statement
theorem NearlyOptimalPPR.Computation.recursive_call_history (m : SolveModel) (n : ℕ) (g : InputGraph n) (s : Fin n)
(α q : ℝ) (ℓ : ℕ) (schedule : BlockSchedule) :
(∀ (a b id : ℕ) (info : CallInformation), a ≤ b →
(recursiveRun m g s α q ℓ schedule a).information id=some info →
(recursiveRun m g s α q ℓ schedule b).information id=some info) ∧
(∀ a b : ℕ, a ≤ b →
(recursiveRun m g s α q ℓ schedule a).closed ⊆ (recursiveRun m g s α q ℓ schedule b).closed) ∧
(∀ a b j : ℕ, a ≤ b →
(∀ k, a ≤ k → k < b → j ≤ (recursiveRun m g s α q ℓ schedule k).top) →
frozenFrame ((recursiveRun m g s α q ℓ schedule b).frames j)=
frozenFrame ((recursiveRun m g s α q ℓ schedule a).frames j)) ∧
(∀ T id : ℕ,
(recursiveRun m g s α q ℓ schedule T).fullSolves id=
((Finset.range T).filter (fun k => fullSolveEvent g (recursiveRun m g s α q ℓ schedule k) id)).card ∧
(recursiveRun m g s α q ℓ schedule T).episodes id=
((Finset.range T).filter (fun k => episodeEvent (recursiveRun m g s α q ℓ schedule k) id)).card) := by sorrySource
Li, Xu, Yang, Zhou, Nearly optimal Personalized PageRank computation, STOC 2027 submission #884, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/884.pdf, Algorithms 6–9 pp.14–22 and finite-prefix bookkeeping in the proof of Lemma 4.4 pp.28–29.