Production bound for a running recursive PageRank call
ProvedNearlyOptimalPPR.Computation.recursive_running_call_productionalgorithm-analysisgraph-theorypagerank
Let be finite reachable snapshots at which the same recursive call is current and the computation is running. Suppose no open budget is exhausted at the final snapshot. If are that call's threshold and scale at the first snapshot, then
Here is charged exterior-push inflow and is the activation charge for that level. The input graph is finite and undirected with a nonisolated seed, , and positive root threshold.
This version of the finite-prefix production estimate permits arbitrary running endpoints. It supplies the inflow bound used to amortize cached solves at a leaf, without assuming termination or requiring a full solve at either endpoint.
Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_work_analysis set_option autoImplicit false open Finset Matrix NearlyOptimalPPR.Computation
Formal statement
theorem NearlyOptimalPPR.Computation.recursive_running_call_production (m : SolveModel) (n : ℕ) (g : InputGraph n) (s : Fin n) (α q : ℝ)
(hα : 0 < α ∧ α < 1) (hq : 0 < q) (hs : 0 < g.graph.degree s)
(ℓ : ℕ) (schedule : BlockSchedule) (a b id : ℕ) (hab : a ≤ b)
(hda : (recursiveRun m g s α q ℓ schedule a).done=false)
(hida : ((recursiveRun m g s α q ℓ schedule a).frames (recursiveRun m g s α q ℓ schedule a).top).id=id)
(hdb : (recursiveRun m g s α q ℓ schedule b).done=false)
(hidb : ((recursiveRun m g s α q ℓ schedule b).frames (recursiveRun m g s α q ℓ schedule b).top).id=id)
(hexb : ¬anyExhausted (recursiveRun m g s α q ℓ schedule b)) :
let run := recursiveRun m g s α q ℓ schedule
let j := (run a).top
(∑ k ∈ Finset.Ico a b, (incomingProduction g α (run k) j+birthProduction g (run k) j)) ≤
2*(kappa ℓ 0 : ℝ)*((run a).frames j).q*((run a).frames j).N := 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, the cached-solve and finite-prefix charge analysis in Section 5 pp.28–29, proof of Lemma 4.4 p.18; Algorithms 6–9.