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
- August 2026 · Development [1]
Robert Krauthgamer and Ohad Petruschka Proved lower bounds for geometric spanners with two hops and asked about unrestricted paths.
Rajesh Jayaram and colleagues Proved a polynomial edge overhead for unrestricted undirected Steiner spanners in every finite norm.
AI contribution
Constant-Stretch High-Dimensional Spanners Require Polynomial Overhead
For every fixed stretch and every finite , there are arbitrarily large n-point subsets of a logarithmic-dimensional binary cube in for which every undirected Steiner C-spanner needs edges for some . Auxiliary vertices, arbitrary nonnegative edge weights and unrestricted path lengths are allowed.
Sources
Publication history
Constant-Stretch High-Dimensional Spanners Require Polynomial Overhead
Daily emails by default, only when there’s an update.