Theorem 4.7 — single-batch terminal augmentation
OpenIncrementalER.Supplement.theorem_4_7data-structureseffective-resistancegraph-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probability
Let be a -hitting set and let contain , where . Given the initialized one-sided leverage-degree oracle and any batch , one uniform randomized exact-real-RAM program returns in charged work with
and, for every fixed vertex ,
The expectation is only over the fresh randomness of this batch algorithm.
Differences from the source:
- encoding: access to the initialized leverage-degree data structure → a one-sided constant-accuracy estimator exposed through a halt-and-resume oracle protocol, with the full query cost added to machine work; reason: this makes oracle access explicit without adding a free instruction to PNormReg
- encoding: expectation over batch randomness → a lower integral over a fresh fair-coin tape, while the retained sets and estimator are fixed outside the integral; reason: exactly preserves the probability scope printed after Theorem 4.7
- generalization: graph edges join distinct vertices → edge-list inputs may also contain loops, ignored by all graph quantities; reason: removing loops preserves the source instance and only decreases the size parameter used in upper bounds
Preamble
import Mathlib import Definitions.Def_IncrementalER_Supplement_theorem47Spec set_option autoImplicit false
Formal statement
namespace IncrementalER.Supplement
/-- **Theorem 4.7** (Goranci et al., STOC 2027 submission, manuscript sha256 a0415fd5…, p.19).
Given the common hitting set, retained sets and a one-sided initialized leverage estimator, a
uniform charged-oracle program augments any one batch with the printed factor-two size, time and
expected average-cost guarantee. The expectation is only over this batch program. -/
theorem theorem_4_7 :
∀ A : ℝ, 0 < A → ∀ q : ℕ,
∃ P : PNormReg.Program, ∃ C : ℝ, ∃ r p : ℕ,
A ≤ C ∧ q ≤ r ∧ theorem47Spec P C r p := 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 4.7, p.19