EADS Talk by Greg Bodwin on 'The 4/3 Additive Spanner Exponent is Tight'
Talk by Greg Bodwin, Stanford Dept. of Computer Science
Title: The 4/3 Additive Spanner Exponent is Tight
Abstract
A +k additive spanner is a sparse subgraph that preserves all pairwise distances up to additive error +k. A classical result in this field states that all graphs have +6 spanners on n^{4/3} edges, but no sparser spanners are known for any constant k. Meanwhile, current lower bound allow for the possibility of constant error spanners on O(n^{1 + eps}) edges for all eps > 0. It is considered a central open problem to prove the existence/nonexistence of these nearly-linear sized additive spanners.
We resolve this question in the negative: there are graphs that provably have no spanners on n^{4/3 - eps} edges, unless the additive error is allowed to be polynomial in n. In this talk, we will describe a simple construction technique that produces one of these graphs. We will then discuss some extensions and implications of this new lower bound.
Joint work with Amir Abboud