Greg Bodwin, University of Michigan

Abstract

Given a large input graph, a spanner is a sparse subgraph with approximately the same shortest path distances as the original, and an emulator is the same but not required to be a subgraph.  Spanners and emulators have natural applications in networking, where it is common for nodes or edges of the input graph to temporarily fail.  This gives rise to an extended notion of "fault tolerant" spanners and emulators, whose distance approximation is robust to these failures.

There has been a recent flurry of progress in this research area in the last 5 years, including faster construction algorithms and better tradeoffs between spanner size, error, and level of fault tolerance. We will survey this progress, explain the new techniques that have enabled it, and overview the major remaining open problems.

See: https://theory.cs.rutgers.edu/theory_seminar