[TcsBu] Algorithms and Theory Seminar

Mahendra Varma, Nithin nvarma at bu.edu
Fri Dec 8 01:41:42 EST 2017


The Algorithms and Theory Seminar this week will happen today from 12 - 1 PM in MCS 148.  Greg Bodwin (MIT) will be speaking about his recent work on fault tolerant spanners. There will be light lunch at 11:45 am.

The title and abstract of the talk are appended. Please note the unusual time and location.

Thank you,

Algorithms and Theory Seminar

Speaker : Greg Bodwin (MIT)
Date and Time: Friday, Dec 8th, 12 - 1 PM
Venue: MCS 148

Title: Optimal Vertex Fault Tolerant Spanners (for fixed stretch)

Abstract: A stretch-k spanner of a graph G is a sparse subgraph H that preserves the distances of G up to a multiplicative error of k.  The tradeoffs between the stretch k and the sparsity of the spanner H are very well understood.  Spanners are often used to model systems like road networks or internet communication.  However, in real life, one has to worry about "failures" in these applications: for example, maybe there are traffic jams or router failures that change the underlying graph. This motivates the study of "fault-tolerant spanners," where H is an f-fault tolerant k-spanner of G if H \ F is a k-spanner of G \ F for any possible set of f "failing" nodes F.

We close the central open problem in fault tolerant spanners by showing that O_k( n^{1 + 1/k} f^{1 - 1/k} ) edges always suffice for an f-fault tolerant (2k-1)-spanner, and that this is optimal (under standard conjectures) in the sense that some graphs will need this many edges.  Additionally, these spanners can be built with an extremely simple and natural "greedy algorithm" that naturally extends the one typically used in the non-faulty setting.  In this talk we will focus mainly on the proof for the case k=2, which is particularly simple, and then give a sketchy overview of the generalization to larger k.

Joint work with Michael Dinitz, Merav Parter, and Virginia Vassilevska Williams.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/tcs-announce/attachments/20171208/4ebd856e/attachment.html>

More information about the tcs-announce mailing list