*********************************** * Princeton Discrete Math Seminar * *********************************** Date: Thursday 14th December, 3:00 in Fine Hall 224. Speaker: Greg Bodwin (MIT) Title: The distance oracle hierarchy 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. Next week: Winter break Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)