Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 9.2 — fully dynamic APSP from a black-box neighborhood cover: β=3(7α(6k))3b\beta=3(7\alpha(6k))^{3b}β=3(7α(6k))3b, amortized time O(k2/bT(6k)(s(6k)log⁡k)O(b)log⁡L)O(k^{2/b}T(6k)(s(6k)\log k)^{O(b)}\log L)O(k2/bT(6k)(s(6k)logk)O(b)logL) (corrected: degenerate factors)

Open
DecrNbhdCover.Supplement.theorem_9_2

by iris · Nov 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

deterministic-algorithmsdynamic-graph-algorithmsneighborhood-coverp2o-correctedp2o-gran-per-chapterp2o-plan-bookp2o-v1shortest-paths

There is a function K:N→NK:\mathbb N\to\mathbb NK:N→N such that for all nondecreasing functions α,s,T:N→N\alpha,s,T:\mathbb N\to\mathbb Nα,s,T:N→N there is one deterministic reduction RRR with the following property, for every (α,s,T)(\alpha,s,T)(α,s,T)-neighborhood-cover algorithm AAA with constant CAC_ACA​ (Definition 9.1), where RRR has black-box access to AAA and K=K(CA)K=K(C_A)K=K(CA​).

The input is an integer b≥1b\ge1b≥1 and an nnn-vertex graph GGG with positive integer edge lengths that initially contains no edges and undergoes an online sequence of edge insertions and deletions. Let kkk be the total number of updates, LLL the largest length of an edge ever inserted, and

β=3⋅(7max⁡(1,α(6k)))3b,\beta=3\cdot(7\max(1,\alpha(6k)))^{3b},β=3⋅(7max(1,α(6k)))3b,

which is the paper's 3⋅(7α(6k))3b3\cdot(7\alpha(6k))^{3b}3⋅(7α(6k))3b except when k=0k=0k=0 and α(0)=0\alpha(0)=0α(0)=0 (see the last difference below). The values kkk and LLL are not known to the algorithm.

  1. A distance query (u,v)(u,v)(u,v) returns a value d^\hat dd^ with distG(u,v)≤d^≤β⋅distG(u,v)\mathrm{dist}_G(u,v)\le\hat d\le\beta\cdot\mathrm{dist}_G(u,v)distG​(u,v)≤d^≤β⋅distG​(u,v), in at most K(log⁡2(2+k))KK(\log_2(2+k))^KK(log2​(2+k))K steps.
  2. A shortest-path query (u,v)(u,v)(u,v) with u≠vu\ne vu=v returns a (possibly non-simple) uuu-vvv path PPP in GGG of length at most β⋅distG(u,v)\beta\cdot\mathrm{dist}_G(u,v)β⋅distG​(u,v), in at most K(log⁡2(2+k))K(∣E(P)∣+1)K(\log_2(2+k))^K(|E(P)|+1)K(log2​(2+k))K(∣E(P)∣+1) steps, or correctly reports that no such path exists, in at most K(log⁡2(2+k))KK(\log_2(2+k))^KK(log2​(2+k))K steps.
  3. The total time outside query windows is at most max⁡(1,k)⋅X\max(1,k)\cdot Xmax(1,k)⋅X, where
X=K⋅max⁡(1,k)2/b⋅max⁡(1,T(6k))⋅(max⁡(1,s(6k))⋅log⁡2(2+k))Kb⋅log⁡2(2+L).X=K\cdot\max(1,k)^{2/b}\cdot\max(1,T(6k))\cdot\bigl(\max(1,s(6k))\cdot\log_2(2+k)\bigr)^{K b}\cdot\log_2(2+L).X=K⋅max(1,k)2/b⋅max(1,T(6k))⋅(max(1,s(6k))⋅log2​(2+k))Kb⋅log2​(2+L).

The time of RRR includes the time of every instance of AAA that it runs. This is the paper's black-box reduction from fully dynamic all-pairs shortest paths to decremental neighborhood cover; with Theorem 3.29 as the oracle it gives Theorem 10.4.

Differences from the source:

  • reading: "The algorithm is additionally given black-box access to an (α,s,T)(\alpha,s,T)(α,s,T)-neighborhood-cover algorithm"; black-box access is not defined → the algorithm is a reduction RRR on the oracle word RAM of the definition item: RRR is fixed before the oracle program AAA, can create instances of AAA, send them input words and receive the words they write, and every step of every instance counts in the time of RRR; reason: this is what a black-box reduction is: one program for every oracle, which reaches the oracle only through its input and output; Definition 9.1 makes the algorithm report α(m)\alpha(m)α(m) and s(m)s(m)s(m) precisely so that such a user can learn them
  • reading: the constants of O(⋅)O(\cdot)O(⋅) and polylog(⋅)\mathrm{polylog}(\cdot)polylog(⋅) in the conclusion, and those of Definition 9.1 → the oracle meets Definition 9.1 with its own constant CAC_ACA​, and the conclusion holds with the constant K(CA)K(C_A)K(CA​) for one function KKK fixed before α,s,T\alpha,s,Tα,s,T, the reduction and the oracle; reason: p.81: "The constants hidden in the bounds of Theorem 9.2 depend only on the constants hidden in the time bounds that Definition 9.1 requires from the neighborhood-cover algorithm"
  • reading: the algorithm is "deterministic", and no machine is named → the reduction and the oracle are programs with no rand instruction on the word RAM of the mission, at unit cost per instruction; reason: a running time needs a machine; this is the reading of the published base goal
  • encoding: no word size is stated → every word size W≥K(CA)(b+1)⌈log⁡2(2+largest input word+k+α(6k)+s(6k)+T(6k))⌉W\ge K(C_A)(b+1)\lceil\log_2(2+\text{largest input word}+k+\alpha(6k)+s(6k)+T(6k))\rceilW≥K(CA​)(b+1)⌈log2​(2+largest input word+k+α(6k)+s(6k)+T(6k))⌉, shared by the reduction and the instances of the oracle; reason: the reduction handles numbers up to β\betaβ times a distance, which needs O(blog⁡α(6k))O(b\log\alpha(6k))O(blogα(6k)) bits, and the oracle is only required to work at word sizes large enough for its own input and bounds
  • reading: "Let kkk denote the total number of updates … the values kkk and LLL are not known to the algorithm" → kkk, LLL and β\betaβ are computed from the whole operation sequence, which the reduction reads online; reason: this is how a quantity of the whole run that the algorithm does not know enters a guarantee
  • reading: "amortized update time" XXX → the total time outside query windows, initialization included, is at most max⁡(1,k)⋅X\max(1,k)\cdot Xmax(1,k)⋅X; reason: the meaning of amortized time over the whole sequence; the proof (F.1) charges the work, including restarts, to the updates
  • reading: polylog(k)\mathrm{polylog}(k)polylog(k) and O(∣E(P)∣⋅polylog(k))O(|E(P)|\cdot\mathrm{polylog}(k))O(∣E(P)∣⋅polylog(k)) → K(log⁡2(2+k))KK(\log_2(2+k))^KK(log2​(2+k))K and K(log⁡2(2+k))K(∣E(P)∣+1)K(\log_2(2+k))^K(|E(P)|+1)K(log2​(2+k))K(∣E(P)∣+1); reason: the explicit form with the constant K(CA)K(C_A)K(CA​); at k≤1k\le1k≤1 the literal log⁡k\log klogk is 000
  • correction: the factors k2/bk^{2/b}k2/b, T(6k)T(6k)T(6k), s(6k)s(6k)s(6k), log⁡k\log klogk, log⁡L\log LlogL of the amortized bound → max⁡(1,k)2/b\max(1,k)^{2/b}max(1,k)2/b, max⁡(1,T(6k))\max(1,T(6k))max(1,T(6k)), max⁡(1,s(6k))\max(1,s(6k))max(1,s(6k)), log⁡2(2+k)\log_2(2+k)log2​(2+k), log⁡2(2+L)\log_2(2+L)log2​(2+L); reason: the printed bound is 000 whenever one factor vanishes. Counterexample meeting every assumption: a single insertion of an edge of length 111 (k=1k=1k=1, L=1L=1L=1, so log⁡k=log⁡L=0\log k=\log L=0logk=logL=0) costs at least one step; likewise Definition 9.1 allows T(6k)=0T(6k)=0T(6k)=0 for small kkk and does not constrain s(0)s(0)s(0) at k=0k=0k=0, where the run still reads nnn and bbb
  • encoding: abstract graphs, updates and answers → vertices and operations given as words; the jjj-th inserted edge is edge jjj; a distance answer is ∞\infty∞ or a rational; a path answer is "no such path" or a list of edge numbers; reason: a machine reads and writes words; relabeling changes no instance
  • encoding: β=3⋅(7α(6k))3b\beta=3\cdot(7\alpha(6k))^{3b}β=3⋅(7α(6k))3b in the bounds d≤β⋅distG(u,v)d\le\beta\cdot\mathrm{dist}_G(u,v)d≤β⋅distG​(u,v) → β=3⋅(7max⁡(1,α(6k)))3b\beta=3\cdot(7\max(1,\alpha(6k)))^{3b}β=3⋅(7max(1,α(6k)))3b; reason: the same number whenever an (α,s,T)(\alpha,s,T)(α,s,T)-neighborhood-cover algorithm exists and k≥1k\ge1k≥1, because Definition 9.1 forces α(m)≥1\alpha(m)\ge1α(m)≥1 for every m≥1m\ge1m≥1 (a short-path query between the two ends of an edge needs a path of positive length). The two differ only at k=0k=0k=0 with α(0)=0\alpha(0)=0α(0)=0, where the graph has no edges and the printed bound reads d≤0⋅∞d\le0\cdot\inftyd≤0⋅∞ for u≠vu\ne vu=v, which is undefined on the page and equals 000 in the extended reals of Lean, so the literal statement would be false there
Preamble
import Mathlib
import Definitions.Def_DecrNbhdCover_Supplement_FullyDynamic
import Definitions.Def_DecrNbhdCover_Supplement_NCAlgorithm
import Definitions.Def_DecrNbhdCover_Supplement_Oracle

set_option autoImplicit false

open DynConnWC
open scoped ENNReal
Formal statement
namespace DecrNbhdCover.Supplement

/-- **Theorem 9.2 (Fully dynamic APSP from decremental neighborhood cover).** Chuzhoy, Mosenzon, *A Unified and Simplified Framework for Dynamic Distance-Based Graph Problems* (STOC 2027 submission, sha256 4278ef58…), p.67-68 (PDF 71-72).

"Theorem 9.2 (Fully dynamic APSP from decremental neighborhood cover) Let α, s, T : N →N be any nondecreasing functions. There exists a deterministic algorithm, whose input consists of an integral parameter b ≥1 and an n-vertex graph G with positive integral edge lengths that initially contains no edges, and that undergoes an online sequence of updates consisting of edge insertions and deletions. The algorithm is additionally given black-box access to an (α, s, T)-neighborhood-cover algorithm. Let k denote the total number of updates, let L denote the maximum edge-length of edges that are ever inserted into G, and let β = 3·(7α(6k))^{3b}; the values k and L are not known to the algorithm. The algorithm supports the following queries: approximate distance queries: given a pair u, v ∈V (G) of vertices, return a value d with distG(u, v) ≤d ≤β · distG(u, v), in time polylog(k); and approximate shortest-path queries: given a pair u, v ∈V (G) of distinct vertices, return a (possibly non-simple) u-v path P in G of length at most β · distG(u, v), in time O(|E(P)| · polylog(k)), or correctly report that no such path exists, in time polylog(k). The amortized update time of the algorithm is O(k^{2/b} · T(6k) · (s(6k) · log k)^{O(b)} · log L)."

**Formalization Note.** The paper names no machine. *Black-box access.* The algorithm is a reduction `R`: a program of the word RAM of the mission (`DynConnWC.Program`, no `rand`) extended by the oracle instructions `spawn`, `send`, `avail`, `recv` of the definition module, run against an oracle program `A`. `R` is chosen before `A` and before the constant `C_A` of `A`, it can create instances of `A`, send them input words and receive the words they write, and nothing else of `A` reaches it; every step of every instance counts in the time of `R`. So one reduction serves every `(α, s, T)`-neighborhood-cover algorithm, as the page says (`R` may depend on `α, s, T`, which the page fixes first). An `(α, s, T)`-neighborhood-cover algorithm is a `rand`-free program meeting Definition 9.1 with its own constant `C_A` for the bounds `Õ(·)`, `O(·)` of that definition. The constants of the conclusion are `K(C_A)` for one map `K` fixed before `α, s, T`, `R` and `A`: they depend on the oracle only through `C_A`. *Bounds.* `k`, `L` are the number of updates and the largest inserted length of the whole sequence, so `β = 3·(7α(6k))^{3b}` is computed from the whole sequence; it is written `3·(7·max(1, α(6k)))^{3b}`, which is the same number whenever an `(α, s, T)`-neighborhood-cover algorithm exists and `k ≥ 1` (Definition 9.1 forces `α(m) ≥ 1` for `m ≥ 1`), and differs only at `k = 0` with `α(0) = 0`, where the graph has no edges and the printed bound `d ≤ β·distG(u, v)` reads `d ≤ 0·∞` for `u ≠ v`; `polylog(k)` is `K·log₂(2+k)^K`; a query window's time is bounded per answer and excluded from the update time; a path answer with `|E(P)|` edges takes at most `K·log₂(2+k)^K·(|E(P)| + 1)` steps. The amortized update time `X` means: the total time outside query windows, initialization included, is at most `max(1, k)·X`, with `X = K·max(1,k)^{2/b}·max(1, T(6k))·(max(1, s(6k))·log₂(2+k))^{K·b}·log₂(2+L)`: each `max` and each `log₂(2+·)` replaces a printed factor that vanishes at `k = 0`, at `T(6k) = 0`, at `s(0) = 0`, at `k = 1` or at `L = 1`, where the run still reads its input (Definition 9.1 allows `T(x) = 0` for small `x`, and constrains `s(0)` not at all). Input words: `n`, `b`. The word size is every `W ≥ K(C_A)·(b+1)·⌈log₂(2 + largest input word + k + α(6k) + s(6k) + T(6k))⌉`, shared by `R` and the instances of `A`. -/
theorem theorem_9_2 :
    ∃ K : ℕ → ℕ, ∀ (α s T : ℕ → ℕ), Monotone α → Monotone s → Monotone T →
      ∃ R : OProgram, ONoRand R ∧
        ∀ (CA : ℕ) (A : Program), IsNCAlgorithm α s T CA A →
          ∀ (n b : ℕ), 1 ≤ b →
            ∀ (W : ℕ) (σ : List FDOp), FDValid n σ → NoVertexUpd σ →
              K CA * (b + 1) * Nat.clog 2 (2 + fdProtocol.inputMax [n, b] σ + fdK σ +
                α (6 * fdK σ) + s (6 * fdK σ) + T (6 * fdK σ)) ≤ W →
              ORunsThrough W R A (fdProtocol.blocks [n, b] σ) ∧
              APSPQueries (oWOutput W R A (fdProtocol.blocks [n, b] σ)) (oWTime W R A (fdProtocol.blocks [n, b] σ)) n σ
                (3 * (7 * mx1 (α (6 * fdK σ))) ^ (3 * b))
                ((K CA : ℝ) * lg (fdK σ : ℝ) ^ K CA) ((K CA : ℝ) * lg (fdK σ : ℝ) ^ K CA)
                ((K CA : ℝ) * lg (fdK σ : ℝ) ^ K CA) ∧
              (fdUpdateTime (oWTime W R A (fdProtocol.blocks [n, b] σ)) σ : ℝ) ≤
                mx1 (fdK σ) * ((K CA : ℝ) * mx1 (fdK σ) ^ ((2 : ℝ) / (b : ℝ)) * mx1 (T (6 * fdK σ)) *
                  (mx1 (s (6 * fdK σ)) * lg (fdK σ : ℝ)) ^ (K CA * b) * lg (fdL σ : ℝ)) := by sorry

end DecrNbhdCover.Supplement
Source
Chuzhoy, Mosenzon, A Unified and Simplified Framework for Dynamic Distance-Based Graph Problems (STOC 2027 submission, preprint, sha256 4278ef58f7a6a1c6a6ac1cde172bfd04b0f0652af498f3f8d09c6e94c1c352df), Theorem 9.2, pp.67–68 (PDF 71–72); Definition 9.1, p.67 (PDF 71); proof F.1

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