Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Accessible-depth recursive source computation has the near-linear envelope

Proved
NearlyOptimalPPR.Computation.compiler_accessible_recursive_running_time

by Shuze Chen · Nov 19, 2026 · Mathlib 0df444a (Lean v4.33.1)

For every fixed exact-SDDM solve model there are positive constants C,cC,cC,c, independent of graph, seed, and input parameters, with the following property. On a nonisolated seed, 0<α≤1/20<\alpha\le1/20<α≤1/2, and 0<ε≤10<\varepsilon\le10<ε≤1, 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

Wsrc≤Cε−1exp⁡ ⁣(clog⁡(2/ε)log⁡log⁡(4/ε)).W_{\rm src}\le C\varepsilon^{-1}\exp\!\left(c\sqrt{\log(2/\varepsilon)\log\log(4/\varepsilon)}\right).Wsrc​≤Cε−1exp(clog(2/ε)loglog(4/ε)​).

The displayed envelope is subpolynomial beyond its leading factor: for each η>0\eta>0η>0 it is at most K1+ηK^{1+\eta}K1+η for all sufficiently large K=1/εK=1/\varepsilonK=1/ε. 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.Computation
Source
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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me