Seminar • Algorithms and Complexity • The Quest for the One True Definition of Fault Tolerant Spanners

Please note: This seminar will take place in DC 2568 and online.

Greg Bodwin, Assistant Professor
Electrical Engineering & Computer Science, University of Michigan

A spanner is a graph sparsifier that approximately preserves shortest path distances. Spanners are often applied in contexts where nodes and edges can temporarily fail. We would like our spanners to still have good approximation properties, even after these failures. How should we formalize this?

We will survey 10 or so papers, spanning the last 20 or so years. We will discuss what they reveal about fault tolerance, how it should (or shouldn't) be defined, and where the area might go next.

To attend this seminar in person, please go to DC 2568. You can also attend virtually on Zoom.