[TcsBu] Algorithms and Theory Seminar

Mahendra Varma, Nithin nvarma at bu.edu
Sun Dec 3 21:10:20 EST 2017

Hi everyone,

Greg Bodwin (MIT)<https://sites.google.com/site/gregbodwin/> will be speaking this week at the Algorithms and Theory Seminar scheduled for Friday (Dec 8th). The title and abstract of the talk are appended. We will announce the exact time and venue of the talk within a couple of days.

Thank you,


Algorithms and Theory Seminar

Speaker : Greg Bodwin (MIT)

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/20171204/2bf57fb9/attachment.html>

More information about the tcs-announce mailing list