Finite-prefix full-solve count in recursive PageRank
ProvedNearlyOptimalPPR.Computation.recursive_full_solve_countalgorithm-analysisgraph-theorypagerank
There is a positive absolute constant such that every recursive PageRank call created on a valid input obeys the following bound at every finite prefix:
Here and are the call's scale and block size, is the depth, , and the teleportation parameter satisfies . The graph is finite and undirected and the seed is nonisolated. The same constant works across graphs, calls, depths, primitive solve models, and block schedules.
This is the full-solve event-count component of Lemma 4.4. It holds for finite prefixes, so it does not use termination as a premise.
Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_work_analysis import Definitions.Def_NearlyOptimalPPR_Computation_push set_option autoImplicit false open NearlyOptimalPPR.Computation
Formal statement
theorem NearlyOptimalPPR.Computation.recursive_full_solve_count :
∃ C : ℝ, 0 < C ∧ ∀ (m : SolveModel) (n : ℕ) (g : InputGraph n) (s : Fin n)
(α ε : ℝ) (ℓ : ℕ) (schedule : BlockSchedule),
(0 < α ∧ α ≤ 1/2) → (0 < ε ∧ ε ≤ 1) → 0 < g.graph.degree s →
∀ (t id : ℕ) (info : CallInformation),
(recursiveRun m g s α (rootThreshold ε ℓ) ℓ schedule t).information id=some info →
((recursiveRun m g s α (rootThreshold ε ℓ) ℓ schedule t).fullSolves id : ℝ) ≤
overhead C 3 ε ℓ*info.scale/info.block := 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, Lemma 4.4 p.18, Lemmas 5.7–5.8 and the finite-prefix counting proof pp.26–29.