CSD Faculty Candidate
— 12:00pm
Location:
In Person and Virtual  ET

NewellSimon 4305 and Zoom
Speaker:
NICOLE WEIN
,
Simons Postdoctoral Leader, Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University
http://people.csail.mit.edu/nwein/
DistanceEstimation in Modern Graphs: Algorithms and Impossibility
The size and complexity of today's graphs present challenges that necessitate the discovery of new algorithms. One central area of research in this endeavor is computing and estimating distances in graphs. In this talk I will discuss two fundamental families of distance problems in the context of modern graphs: Diameter/Radius/Eccentricities and Hopsets/Shortcut Sets.
The bestknown algorithm for computing the diameter (largest distance) of a graph is the naive algorithm of computing allpairs shortest paths and returning the largest distance. Unfortunately, this can be prohibitively slow for massive graphs. Thus, it is important to understand how fast and how accurately the diameter of a graph can be approximated. I will present tight bounds for this problem via conditional lower bounds from finegrained complexity.
Secondly, for a number of settings relevant to modern graphs (e.g. parallel algorithms, streaming algorithms, dynamic algorithms), distance computation is more efficient when the input graph has low hopdiameter. Thus, a useful preprocessing step is to add a set of edges (a hopset) to the graph that reduces the hopdiameter of the graph, while preserving important distance information. I will present progress on upper and lower bounds for hopsets.
—
Nicole Wein is a Simons Postdoctoral Leader at DIMACS at Rutgers University. Previously, she obtained her Ph.D. from MIT advised by Virginia Vassilevska Williams. She is a theoretical computer scientist and her research interests include graph algorithms and lower bounds including in the areas of distanceestimation algorithms, dynamic algorithms, and finegrained complexity.
Faculty Host: Anupam Gupta In Person and Zoom Participation. See announcement.