Theorem 4.2 — retained terminal sets with constant average insertion cost
OpenIncrementalER.Supplement.theorem_4_2effective-resistancegraph-algorithmsmultiplicative-weightsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probability
For every connected positive-capacity graph with quasipolynomial capacity ratio and every real , one uniform randomized exact-real-RAM program computes sets such that
for every vertex . With high probability the sets all contain one common -hitting set , satisfy , and are produced in charged work.
Differences from the source:
- encoding: compute a sequence with O-tilde size/time and high probability → one admissible PNormReg program whose output memory contains s, S0, and every Qi, with uniform constants/exponents and one failure event; reason: fixes the unnamed machine and the p.10 asymptotic conventions while retaining the complete sequence output
- 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_theorem42Spec set_option autoImplicit false
Formal statement
namespace IncrementalER.Supplement
/-- **Theorem 4.2** (Goranci et al., STOC 2027 submission, manuscript sha256 a0415fd5…, p.16).
One uniform program produces the whole retained sequence, its common `k`-hitting set, the pointwise
average insertion-cost guarantee, every size bound, total work and the simultaneous
high-probability event. -/
theorem theorem_4_2 :
∀ A : ℝ, 0 < A → ∀ q : ℕ, ∀ c : ℝ, 1 < c →
∃ P : PNormReg.Program, ∃ C : ℝ, ∃ r p : ℕ,
A ≤ C ∧ q ≤ r ∧ theorem42Spec 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 4.2, p.16