The Distance Oracle Hierarchy

26 Feb
Theory of Computation Seminar
Greg Bodwin, MIT
Monday, February 26, 2018 -
1:15pm to 2:15pm
Pierce Hall 213 (Brooks Room)

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 thresholds.  The proof is graph-theoretic and relies on building large families of graphs with large discrepancies in their metrics.

Speaker Bio: 

 I am in the fifth and final year of my PhD, currently at MIT, advised by Virginia Vassilevska Williams.  My research sits at the boundary of extremal combinatorics, graph theory, geometry, and algorithm design.  A lot of my work so far deals with the structure of shortest paths in graphs or general metrics, covering topics such as spanners, distance preservers, and more.

Carol Harlow