CS Events

Seminar

The Distance Oracle Hierarchy

 

Download as iCal file

Wednesday, December 06, 2017, 11:00am

 

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.

Includes joint work with Amir Abboud and Seth Pettie.

Speaker: Greg Bodwin

Bio

NULL

Location : CoRE 301

Committee

Pranjal Awasthi and Shubhangi Saraf

Event Type: Seminar

Abstract: 

Organization

MIT