This talk is a paragon of what a colloquium talk should be. As the abstract indicates, the speaker focused on giving an insightful and educational survey of a research direction, providing a wide and yet nuanced picture.

The research direction is *fault tolerant spanners and emulators*,
where the stretch is measured wrt to the residual graph
(when considering all relevant fault patterns).
Key parameters include allowed stretch (i.e, $k$),
number of faulty components (i.e., $f$),
whether these are vertices or edges,
and whether the desired output should be
a subgraph of the original graph
or a subgraph of the all-pairs distance closure (called emulator).

Specifically, wlog, it suffices to consider the case that $k$ is an odd integer; hence, we let $k=2t-1$. In the non-faulty case, a $(2t-1)$-spanner having $O(n^{1+(1/t)})$ edges can be constructed efficiently, and a $(2t-1)$-emulator cannot have less edges. When $f$ faults are allowed, the first two cases (i.e., $k=3$ and $k=5$) manifest fundamentally different behavior:

- For stretch $k=3$ (i.e., $t=2$), emulators are not better than spanners, and there is no difference between vertex and edge failures. Specifically, in all cases the ``cost'' of fault-tolerance is a factor of $sqrt(f)$ in the number of required edges.
- For stretch $k=5$ (i.e., $t=3$),
emulators are better than spanners,
and there is a difference between vertex and edge failures.
Specifically, emulators for edge-failures come for free
(i.e., the number of required edges is essentially
as in the non-faulty case), whereas this is not the
case in the other three combinations.
In fact, all results extend to any odd $t$
(equiv $k$ congruent to 1 mod 4);
that is, for stretch $k=2t-1$ (s.t. $t$ is odd),
- For spanners, edge-fault-tolerant comes at a cost of a factor of $f^{0.5+(1/2t)}$ in the number of required edges.
- For spanners, vertex-fault-tolerant comes at a cost of a factor of $f^{1-(1/t)}$ in the number of required edges.
- For emulators, vertex-fault-tolerant comes at a cost of a factor of $f^{0.5+(1/2t)}$ in the number of required edges.

Given a large input graph, a k-spanner is a sparse subgraph that preserves the shortest path distances of the original within an approximation factor of k. When this distance approximation is robust to f failing nodes or edges, the spanner is f-fault tolerant. Fault tolerant spanners and their relatives arise commonly in networking and distributed computing.

There has been a recent flurry of progress on fault tolerant spanners and their relatives, including faster construction algorithms and better tradeoffs between spanner size, error, and level of fault tolerance. We will survey this progress, spanning a sequence of 7 papers over the last 5 years. We will explain the new techniques that have enabled progress, the problems that have been solved, and the problems that remain open.

Back to list of Oded's choices.