Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.3 — episode mass and cache volume

Open
NearlyOptimalPPR.Computation.Supplement.episode_budget

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-algorithmsnumerical-analysisp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1personalized-pagerank

Fix a published exact-SDDM primitive model. Let GGG be a finite simple unweighted undirected graph given by adjacency lists, sss a nonisolated seed, 0<α≤1/20<\alpha\le1/20<α≤1/2, 0<ε≤10<\varepsilon\le10<ε≤1, and bbb any integer with 1≤b≤N=96/ε1\le b\le N=96/\varepsilon1≤b≤N=96/ε. Put q=ε/96q=\varepsilon/96q=ε/96. Consider the prescribed Algorithm 5 execution, using the published depth-zero adapter and its operational ledger.

At every recorded endpoint of every entered episode in every finite prefix, let μ0\mu_0μ0​ be the active work-residual mass in that episode's actual drained starting snapshot, μ\muμ its current active mass, and WWW its current budget charge. Then

μ≤μ0+W.\mu\le\mu_0+W.μ≤μ0​+W.

For every permitted cache solve on CCC in that prefix,

W<Q,vol⁡(C)<2b.W<Q,\qquad \operatorname{vol}(C)<2b.W<Q,vol(C)<2b.

The endpoint account includes the update that crosses the budget, while the cache bound is required before a solve. The algorithm itself opens Q=max⁡(μ0,qb)Q=\max(\mu_0,qb)Q=max(μ0​,qb) and θ=Q/b\theta=Q/bθ=Q/b before FullSolve. This controls the size of caches used by the companion theorem.

Differences from the source:

  • encoding: finite simple unweighted undirected adjacency-list graph, a seed, real parameters, and a positive integer block → the published InputGraph on Fin n with s : Fin n, real alpha and epsilon, and b : Nat with 1 <= b <= 96/epsilon; reason: finite labeling and positive natural blocks represent exactly the source inputs, including graphs with other isolated vertices
  • encoding: Algorithm 5 with idealized exact FullSolve and CacheSolve operations → finite iteration of the published depth-zero recursive transition with threshold epsilon/96 and fixed schedule [b], plus the isolated-source wrapper and an erasing ledger; reason: root_threshold and coreRun_nonisolated prove the threshold and routine identities, run_core proves ledger erasure, and the theorem establishes that a legal block is not clamped
  • encoding: valid finite execution prefixes and episodes → prefixes obtained only by iterating the operational transition, with recorded episode-entry and post-operation snapshots; reason: no residual, cache-size, termination or cost invariant is assumed; crossing updates and the current partial episode are retained
Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_Supplement_ledger

set_option autoImplicit false
Formal statement
namespace NearlyOptimalPPR.Computation.Supplement

/-- Li, Xu, Yang, Zhou, STOC 2027 submission #884 (October 2026),
Lemma 3.3 p.9, proof p.13. Endpoints include the crossing update. -/
theorem episode_budget (m : SolveModel) (n : ℕ) (g : InputGraph n) (s : Fin n)
    (α ε : ℝ) (b : ℕ) (hα : 0 < α) (hαhalf : α ≤ 1 / 2)
    (hε : 0 < ε) (hεone : ε ≤ 1) (hb : 1 ≤ b) (hbN : (b : ℝ) ≤ scale ε)
    (hs : 0 < g.graph.degree s) (t : ℕ) :
    let l := run m g s α ε b t
    (∀ ep ∈ l.endpoints,
      activeMass ep.stop ≤ activeMass ep.start + (ep.stop.frames 0).W) ∧
    (∀ C, event g l.core = .cacheSolve C →
      (l.core.frames 0).W < (l.core.frames 0).Q ∧
      (volumeNat g C : ℝ) < 2 * (b : ℝ)) := by sorry

end NearlyOptimalPPR.Computation.Supplement
Source
Rong-Hua Li, Quanqing Xu, Yichun Yang, Junjie Zhou, STOC 2027 submission #884 (October 2026), Lemma 3.3, p. 9 (printed = PDF); canonical source.pdf, sha256 17a68253bbd187a44704374a465f62c34c8d7628c44b48c160e903ed3300bdb4; proof p.13

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