[theory-seminar] Theory Lunch 10/22: Greg Bodwin on Additive Spanners

[Dan Michael Stubbs]

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>