Search Mailing List Archives
[theory-seminar] Theory Lunch 10/22: Greg Bodwin on Additive Spanners
Dan Michael Stubbs
dstubbs at stanford.edu
Tue Oct 20 21:30:53 PDT 2015
Theory. Lunch. What's not to like? Be there. The speaker will be Greg Bodwin.
-dan
----------------
Title:
The n^{4/3} Additive Spanner Bound 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 major 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20151021/98cf7d41/attachment.html>
More information about the theory-seminar
mailing list