Number of full solves with large incoming or activation charge
ProvedNearlyOptimalPPR.Computation.recursive_large_input_countalgorithm-analysisgraph-theorypagerank
Let be full-solve states of one recursive call, with initial threshold , scale and block size . For consecutive snapshots define
If and for every , then
Here is charged exterior-push inflow and . The finite undirected graph has a nonisolated seed, , and positive root threshold. This finite-prefix estimate pays for one class of exceptional full solves in Lemma 4.4.
Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_work_analysis open Finset Matrix NearlyOptimalPPR.Computation
Formal statement
theorem NearlyOptimalPPR.Computation.recursive_large_input_count (m : SolveModel) (n : ℕ) (g : InputGraph n) (s : Fin n) (α q : ℝ)
(hα : 0 < α ∧ α < 1) (hq : 0 < q) (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).q*(st.frames j).block/8 ≤ fullPairInput g α ℓ run j τ i) →
(E.card : ℝ) ≤ 80*(kappa ℓ 0 : ℝ)*(st.frames j).N/(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.