Classification of a full solve that fails to halve residual mass
ProvedNearlyOptimalPPR.Computation.recursive_nonhalving_full_solvealgorithm-analysisgraph-theorypagerank
Consider full solves of one recursive call, where the solve at was requested after a successful episode return. Write and for the active domains at these snapshots, and for their residual masses, and for the vertices whose virtual potential more than doubles in the solve at . Put
If , then
The quantities are the initial call threshold and block size, and . The graph is finite and undirected with a nonisolated seed, , and positive root threshold.
This is the exact-solve finite-prefix form of Lemma 5.8: failure of mass halving is paid for either by substantial incoming/discovery charge or by substantial potential doubling.
Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_work_analysis open Finset Matrix NearlyOptimalPPR.Computation
Formal statement
theorem NearlyOptimalPPR.Computation.recursive_nonhalving_full_solve (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)
(ha : fullSolveEvent g (recursiveRun m g s α q ℓ schedule a) id)
(hb : fullSolveEvent g (recursiveRun m g s α q ℓ schedule b) id)
(hf : currentPC (recursiveRun m g s α q ℓ schedule (a-2))=.finishEpisode) :
let run := recursiveRun m g s α q ℓ schedule
let j := (run a).top
let H := ((run a).frames j).active
let F := ((run b).frames j).active
let μ := ∑ v ∈ H, ((run a).frames j).residual v
let μnext := ∑ v ∈ F, ((run b).frames j).residual v
let J := (∑ k ∈ Finset.range (b-(a+1)), incomingProduction g α (run (a+1+k)) j)+
4*(kappa ℓ 0 : ℝ)*((run a).frames j).q*(volumeNat g (F \ H) : ℝ)
μ/2 ≤ μnext → μ/4 ≤ J ∨
(((run a).frames j).block : ℝ)/(64*(kappa ℓ 0 : ℝ)) <
(volumeNat g (fullSolveDoubles g α (run a) j) : ℝ) := 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, Lemmas 5.7–5.8 pp.26–28 and the finite-prefix event-counting proof of Lemma 4.4 pp.28–29; Lemma 4.4 statement p.18.