- Series
- ACO Student Seminar
- Time
- Friday, February 9, 2018 - 1:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Greg Bodwin – CS, MIT – gbodwin@mit.edu – https://sites.google.com/site/gregbodwin/
- Organizer
- He Guo

A lot of well-studied problems in CS Theory are about making
“sketches” of graphs that occupy much less space than the graph itself,
but where the shortest path distances of the graph can still be
approximately recovered from the sketch. For example, in the literature
on Spanners, we seek a sparse subgraph whose distance metric
approximates that of the original graph. In Emulator literature, we
relax the requirement that the approximating graph is a subgraph. Most
generally, in Distance Oracles, the sketch can be an arbitrary data
structure, so long as it can approximately answer queries about the
pairwise distance between nodes in the original graph.
Research on these objects typically focuses on optimizing the
worst-case tradeoff between the quality of the approximation and the
amount of space that the sketch occupies. In this talk, we will survey a
recent leap in understanding about this tradeoff, overturning the
conventional wisdom on the problem. Specifically, the tradeoff is not
smooth, but rather it follows a new discrete hierarchy in which the
quality of the approximation that can be obtained jumps considerably at
certain predictable size thresholds. The proof is graph-theoretic and
relies on building large families of graphs with large discrepancies in
their metrics.