Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

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

Dan Michael Stubbs dstubbs at
Tue Oct 20 21:30:53 PDT 2015

Theory.  Lunch.  What's not to like?  Be there.   The speaker will be Greg Bodwin.



The n^{4/3} Additive Spanner Bound is Tight

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: <>

More information about the theory-seminar mailing list