Constant-stretch spanners in high dimensions

A spanner is a weighted graph whose shortest-path distances approximate the distances in a given point set. The question is how many edges are needed when the points lie in high dimension and the approximation factor is fixed.

Why it matters and what counts as progress

Why it matters: The lower bound rules out near-linear-size graphs that preserve all distances up to a fixed constant in this model, even with auxiliary vertices.

What counts as progress: Bounds depend on the norm, dimension, approximation factor, and whether auxiliary vertices or limits on path length are allowed.

How the problem developed

  1. August 2026 · Development [1]

    Robert Krauthgamer and Ohad Petruschka Proved lower bounds for geometric spanners with two hops and asked about unrestricted paths.

  2. 13 Nov 2026 · Proof [2][3][4]

    Rajesh Jayaram and colleagues Proved a polynomial edge overhead for unrestricted undirected Steiner spanners in every finite ℓp\ell _{p} norm.

AI contribution

Constant-Stretch High-Dimensional Spanners Require Polynomial Overhead

Rajesh Jayaram, Vahab Mirrokni, Erik Waingarten, David P. Woodruff, Goran Zuzic

For every fixed stretch C≥1C \ge 1 and every finite p≥1p \ge 1, there are arbitrarily large n-point subsets of a logarithmic-dimensional binary cube in ℓp\ell _{p} for which every undirected Steiner C-spanner needs Ω(n(1+c))\Omega (n^{(1+c)}) edges for some c=c(C,p)>0c = c(C,p)>0. Auxiliary vertices, arbitrary nonnegative edge weights and unrestricted path lengths are allowed.

AI involvementAI-autonomous
ImportanceNotable
Technical verificationFormal (Lean)
Human understandingFew
Paper date:

Sources

  1. Krauthgamer and Petruschka’s earlier bounds and open question
  2. Original manuscript
  3. AI disclosure in the manuscript
  4. Lean proof of the two main bounds
Publication history