Accessible-depth recursive source computation has the near-linear envelope
ProvedNearlyOptimalPPR.Computation.compiler_accessible_recursive_running_timeFor every fixed exact-SDDM solve model there are positive constants , independent of graph, seed, and input parameters, with the following property. On a nonisolated seed, , and , use the depth specified by the charged integer-power preparation search. The canonical recursive source computation terminates after a finite prefix and its charged source work satisfies
The displayed envelope is subpolynomial beyond its leading factor: for each it is at most for all sufficiently large . This theorem concerns the canonical source computation at the depth realized by parameter preparation; separate simulation theorems transfer the bound to machine instructions.
Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_compiler_runtime import Definitions.Def_NearlyOptimalPPR_Computation_compiler_buffers open Finset Matrix open scoped ENNReal set_option autoImplicit false noncomputable section attribute [local instance] Classical.propDecidable
Formal statement
namespace NearlyOptimalPPR.Computation
open SparseQueue
theorem compiler_accessible_recursive_running_time (m : SolveModel) :
∃ C c : ℝ, 0 < C ∧ 0 < c ∧ subpolynomialEnvelope C c ∧
∀ (n : ℕ) (g : InputGraph n) (s : Fin n) (α ε : ℝ),
0 < α → α ≤ 1/2 → 0 < ε → ε ≤ 1 → 0 < g.graph.degree s →
let ℓ := accessibleDepth (1/ε)
recursiveWork m g s α ε ℓ [] ≤ ENNReal.ofReal (envelope C c ε) ∧
∃ t, (recursiveRun m g s α (rootThreshold ε ℓ) ℓ [] t).done=true := by sorry
end NearlyOptimalPPR.ComputationSource
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, Lemmas4.4–4.5, pp.17–19; accessible integer-power depth used in the charged implementation.