Number of full solves with large potential-doubling volume
ProvedNearlyOptimalPPR.Computation.recursive_large_doubling_countalgorithm-analysisgraph-theorypagerank
Let be full-solve states of one recursive PageRank call. Suppose selects solves whose doubling sets satisfy
Then
Here is the root threshold with , are the call's initial scale and block size, and . The finite undirected graph has a nonisolated seed and .
This count combines the weighted doubling bound with the volume bound of the active domain. It controls the potential-doubling exceptions in the finite-prefix proof of Lemma 4.4.
Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_work_analysis open Finset Matrix NearlyOptimalPPR.Computation
Formal statement
theorem NearlyOptimalPPR.Computation.recursive_large_doubling_count (m : SolveModel) (n : ℕ) (g : InputGraph n) (s : Fin n) (α q : ℝ)
(hα : 0 < α ∧ α ≤ 1/2) (hq : 0 < q ∧ q ≤ 1) (hs : 0 < g.graph.degree s)
(ℓ : ℕ) (schedule : BlockSchedule) (τ : ℕ → ℕ) (hτ : StrictMono τ) (T id : ℕ)
(hfull : ∀ i ≤ T, fullSolveEvent g (recursiveRun m g s α q ℓ schedule (τ i)) id)
(E : Finset ℕ) (hE : E ⊆ Finset.range T) :
let run := recursiveRun m g s α q ℓ schedule
let st := run (τ 0)
let j := st.top
(∀ i ∈ E, ((st.frames j).block : ℝ)/(64*(kappa ℓ 0 : ℝ)) ≤
(volumeNat g (fullSolveDoubles g α (run (τ i)) j) : ℝ)) →
(E.card : ℝ) ≤ 384*(kappa ℓ 0 : ℝ)*(st.frames j).N*
(Real.log (2/q)/Real.log 2)/(st.frames j).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, 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.