Stack thresholds and scales in recursive PageRank
ProvedNearlyOptimalPPR.Computation.recursive_stack_scalesalgorithm-analysisgraph-theorypagerank
At every finite operational prefix with positive root threshold, open recursive levels satisfy
and every open episode budget satisfies
Every suspended ancestor is in the child-return control state. These relations express the parameters passed to a child and the budget established at episode entry in Algorithms 6–9.
This protocol invariant supports finite-prefix work and return reasoning. It assumes no accuracy, termination or work conclusion. As a structural statement about the operational transitions, it does not require a teleportation-range or nonisolated-seed premise.
Formalization Note The threshold-passing and suspended-control clauses hold for every root threshold. The scale clause uses its positivity.
Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_work_analysis set_option autoImplicit false open Finset Matrix NearlyOptimalPPR.Computation
Formal statement
theorem NearlyOptimalPPR.Computation.recursive_stack_scales (m : SolveModel) (n : ℕ) (g : InputGraph n) (s : Fin n) (α q : ℝ)
(ℓ : ℕ) (schedule : BlockSchedule) (t : ℕ) :
let st := recursiveRun m g s α q ℓ schedule t
ThresholdRelation st ∧ StackInvariant st ∧ (0 < q → ScaleInvariant st) := 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 the stack/call bookkeeping used in the finite-prefix proof of Lemma 4.4 pp.28–29.