Per-level work recurrences for recursive PageRank
ProvedNearlyOptimalPPR.Computation.recursive_work_recurrencesalgorithm-analysisgraph-theorypagerank
Fix an exact-solve primitive model. There are positive constants and a positive integer such that the uniform work envelopes of created recursive PageRank calls satisfy the following recurrences. Put
For a call scale and block size specified by its schedule,
and at a leaf,
Here is the supremum of the charged work of actual created calls at level and scale , including descendants and completed budget-crossing updates. Its definition assigns infinite work to an unclosed call. The constants depend only on the fixed primitive model and work uniformly for , all depths, and all block schedules. These are the quantitative recurrences of Lemma 4.4.
Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_work_analysis import Definitions.Def_NearlyOptimalPPR_Computation_push set_option autoImplicit false open Finset Matrix NearlyOptimalPPR.Computation open scoped ENNReal
Formal statement
theorem NearlyOptimalPPR.Computation.recursive_work_recurrences (m : SolveModel) :
∃ (C : ℝ) (c : ℕ), 0 < C ∧ 0 < c ∧ ∀ (ε : ℝ) (ℓ : ℕ) (schedule : BlockSchedule),
0 < ε → ε ≤ 1 →
let P := overhead C c ε ℓ
(∀ (j : ℕ) (N : ℝ), j < ℓ → 1 ≤ N → let b := blockScale schedule ℓ j N
workEnvelope m ε ℓ schedule j N ≤ ENNReal.ofReal P*
(ENNReal.ofReal (N^2/b)+ENNReal.ofReal (N/b)*workEnvelope m ε ℓ schedule (j+1) b)+ENNReal.ofReal (P*N)) ∧
(∀ N : ℝ, 1 ≤ N → let b := blockScale schedule ℓ ℓ N
workEnvelope m ε ℓ schedule ℓ N ≤ ENNReal.ofReal (P*(N^2/b+N*b))) := 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 and its finite-prefix counts, termination argument, and work accounting pp.28–29.