Theorem 2.1 — terminal-robust sets under oblivious terminal requests
OpenIncrementalER.Supplement.theorem_2_1data-structureseffective-resistancegraph-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probability
Fix a quasipolynomial capacity-ratio regime and a failure exponent . For every connected positive-capacity multigraph with vertices and edge occurrences, every real , and every oblivious sequence of requests, one uniform randomized exact-real-RAM program maintains online such that:
- is a -hitting set, , and ;
- the expected sum of the leverage degrees of vertices added and removed, evaluated in the corresponding new and old terminal sets, is ;
- .
The total charged work is , and the whole sequence is correct with probability at least .
Differences from the source:
- encoding: informal algorithm, O-tilde bounds, expectation, and high probability → one admissible PNormReg exact-real-RAM program with uniform constants/exponents, lower-integral expectation, and a single coin-tape failure event; reason: this fixes the machine and the p.10 asymptotic conventions without changing any source instance
- encoding: capacitated multigraph used by Laplacian quantities → an edge list for multiplicity and work, collapsed to summed conductances only for Laplacian, leverage, and hitting quantities; reason: parallel edges have exactly the same Laplacian and random-walk conductances after summation
- generalization: graph edges join distinct vertices → edge-list inputs may also contain loops, which are ignored by every conductance, Laplacian, resistance, leverage, Schur-complement, and hitting-set quantity; reason: deleting the loops gives a source instance with identical mathematical outputs and no larger input-size bounds
Preamble
import Mathlib import Definitions.Def_IncrementalER_Supplement_theorem21Spec set_option autoImplicit false
Formal statement
namespace IncrementalER.Supplement
/-- **Theorem 2.1** (Goranci, Kyng, Probst Gutenberg, Zhao, Zöcklein,
*Incremental All-Pairs Effective Resistance in Almost-Linear Time*, STOC 2027 submission,
manuscript sha256 a0415fd5…, pp.7,14).
For every fixed quasipolynomial capacity-ratio regime and high-probability exponent, one admissible
exact-real-RAM program maintains terminal sets for an oblivious online request sequence with all
three printed guarantees: size and containment, expected two-sided leverage-change mass, and
unweighted recourse, together with the printed total-work and simultaneous high-probability bounds.
**Formalization Note.** `theorem21Spec` spells out the online cell protocol, the `k`-hitting-set
congestion parameter, `Õ` factors, both directions of leverage mass, recourse, total work and the
single whole-sequence failure event. -/
theorem theorem_2_1 :
∀ A : ℝ, 0 < A → ∀ q : ℕ, ∀ c : ℝ, 1 < c →
∃ P : PNormReg.Program, ∃ C : ℝ, ∃ r p : ℕ,
A ≤ C ∧ q ≤ r ∧ theorem21Spec P C r p c := 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 2.1, pp.7 and 14