Theorem 5.1 — adaptive one-sided leverage-degree queries
OpenIncrementalER.Supplement.theorem_5_1adaptive-algorithmsdata-structureseffective-resistancegraph-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Fix quasipolynomial capacity, failure, and polynomial-query regimes. For every connected positive-capacity graph, every real , every , and every -hitting set of size , uniform preprocessing and query programs support polynomially many adaptive calls LeverageDegree with and .
Every returned estimate is simultaneously one-sided,
with high probability. Initialization uses charged work and each query uses work, even when its set and vertex depend on the full preceding transcript.
Differences from the source:
- encoding: U is passed by pointer to a membership oracle → U is exposed as a random-access characteristic vector and membership is one charged indirect integer-memory load; reason: this is a concrete PNormReg pointer implementation and does not reveal anything beyond membership
- encoding: polynomially many adaptive queries with high probability → for each fixed polynomial exponent, every transcript strategy is quantified before the fair-coin failure event, which simultaneously covers all its queries; reason: preserves adaptivity while keeping the adversary independent of future random bits
- 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_theorem51Spec set_option autoImplicit false
Formal statement
namespace IncrementalER.Supplement
/-- **Theorem 5.1** (Goranci et al., STOC 2027 submission, manuscript sha256 a0415fd5…, p.29).
For every fixed capacity, failure and polynomial-query regime, preprocessing and query programs
answer polynomially many transcript-adaptive membership-oracle queries with the printed one-sided
`(1+epsilon)` guarantee, initialization/query work and one simultaneous high-probability event. -/
theorem theorem_5_1 :
∀ A : ℝ, 0 < A → ∀ q : ℕ, ∀ c kappa : ℝ, 1 < c → 0 < kappa →
∃ Pre Qry : PNormReg.Program, ∃ C : ℝ, ∃ r p : ℕ,
A ≤ C ∧ q ≤ r ∧ theorem51Spec Pre Qry C r p c kappa := 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 5.1, p.29