Theorem 6.1 — dynamic low-recourse vertex sparsifier
OpenIncrementalER.Supplement.theorem_6_1dynamic-algorithmseffective-resistancegraph-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1spectral-sparsification
Let have active vertex set , initial edge occurrences, , capacity ratio , and protected set . Let and . Under batches of legal vertex insertions and deletions, edge insertions and deletions, and protected-terminal insertions, assume no protected vertex is deleted and
for every distinct surviving throughout the sequence.
One uniform randomized exact-real-RAM program maintains and a positive-capacity multigraph supported on such that ,
, and . Against an oblivious sequence of at most elementary updates, correctness is high probability, expected total output recourse is , and expected total work including initialization is for an absolute .
Differences from the source:
- encoding: changing finite vertex set and multigraph → an active subset of one finite ambient pool and stable natural identifiers for edge occurrences; reason: every source update sequence embeds in a sufficiently large pool, and identifiers preserve parallel-edge multiplicity and exact deletion
- encoding: graph H supported on T and Loewner approximation to SC(G,T) → a decoded positive-capacity edge list supported on T and PSD differences against the Schur complement over the active set; reason: this is the same multigraph and matrix order, while excluding inactive ambient vertices from elimination
- encoding: expected size, recourse, and work → lower integrals of nonnegative edge counts, multiset edge/vertex changes, and charged instructions; reason: prevents non-integrable expectations from receiving Lean's junk value zero
- generalization: graph edges join distinct vertices → initial and inserted edge lists may also contain loops, ignored by all graph quantities; reason: removing loops preserves every source graph and update while only decreasing edge-count upper bounds
Preamble
import Mathlib import Definitions.Def_IncrementalER_Supplement_theorem61Spec set_option autoImplicit false
Formal statement
namespace IncrementalER.Supplement
/-- **Theorem 6.1** (Goranci et al., STOC 2027 submission, manuscript sha256 a0415fd5…, p.37).
One uniform online exact-real-RAM program maintains the terminal set and approximate Schur
complement through the full batch-update interface, with every printed output, capacity-ratio,
effective-resistance, adversary, update-budget, expected recourse and expected work clause. -/
theorem theorem_6_1 :
∀ A : ℝ, 0 < A → ∀ q : ℕ, ∀ c : ℝ, 1 < c →
∃ P : PNormReg.Program, ∃ C : ℝ, ∃ r : ℕ, ∃ cOut : ℝ,
A ≤ C ∧ q ≤ r ∧ theorem61Spec P C r c cOut := by sorry
end IncrementalER.Supplement
Source
Goranci, Kyng, Probst Gutenberg, Zhao, Zöcklein, Incremental All-Pairs Effective Resistance in Almost-Linear Time, STOC 2027 submission (manuscript sha256 a0415fd5…), Theorem 6.1, p.37