Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

General-weight adapter above the exact-recomputation threshold

Proved
DecrAlmostLinearSSSP.Decremental.normal_domain_sssp_adapter

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

algorithmsgraph-theoryshortest-paths

Assume one fixed deterministic scalar RAM program maintains approximate source distances on valid inputs with at least two vertices, weights bounded by the square of the size bound, and accuracy strictly between 1/m1/m1/m and 111. Suppose its total charged maintenance work is at most Cma(m)/ϵCma(m)/\epsilonCma(m)/ϵ, where C>0C>0C>0 and aaa is positive and subpolynomial.

Then a fixed deterministic scalar RAM adapter maintains the full distance array for every valid input with n≥2n\ge2n≥2, arbitrary integer weight bound W≥1W\ge1W≥1, and 1/m<ϵ≤11/m<\epsilon\le11/m<ϵ≤1. For a positive constant DDD and positive subpolynomial function bbb, its charged work satisfies

work⁡≤Dmb(m)ϵ−1max⁡(1,log⁡2W).\operatorname{work}\le Dmb(m)\epsilon^{-1}\max(1,\log_2 W).work≤Dmb(m)ϵ−1max(1,log2​W).

The adapter terminates after initialization and every legal deletion prefix, maintains simultaneous multiplicative accuracy and exact unreachability, and answers a stored-array query in nine charged instructions. The program and bounds are uniform over all input parameters and streams. This isolates the general-weight reduction needed to extend the polynomial-weight theorem to the full domain.

Preamble
import Mathlib
import Definitions.Def_DecrAlmostLinearSSSP_Decremental_Adapters
set_option autoImplicit false
open scoped ENNReal NNReal
open DecrAlmostLinearSSSP.Decremental
Formal statement
theorem DecrAlmostLinearSSSP.Decremental.normal_domain_sssp_adapter
    (p : Program) (C : ℝ) (a : ℕ → ℝ) (queryBound : ℕ)
    (hC : 0 < C) (ha : Subpolynomial a)
    (hpoly : ∀ x : Input, x.Valid → 2 ≤ x.n → x.W ≤ x.size^2 →
      1/(x.size : ℝ) < x.accuracy → x.accuracy < 1 → Maintains p C a queryBound false x) :
    ∃ (host : Program) (D : ℝ) (b : ℕ → ℝ), 0 < D ∧ Subpolynomial b ∧
      ∀ i : Input, i.Valid → 2 ≤ i.n → 1/(i.size : ℝ) < i.accuracy → Maintains host D b 9 true i := by sorry
Source
Cui, Li, Miao and Wang, Partially Dynamic Single-Source Shortest Paths in Almost-Linear Time, October 2026 submission #912, https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/912.pdf, p.4, unnumbered arbitrary-weight scaling reduction; finite scalar RAM implementation and explicit adapter constants formalize this reduction.

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