Nicole Wein, DIMACS

Abstract

Due to the increasing size and complexity of today's graphs, there is a need for new algorithms that meet their demands. One central area in this endeavor is computing and estimating distances in graphs. In this talk I will discuss two families of distance problems in the context of modern graphs: Diameter/Radius/Eccentricities and Hopsets/Shortcut Sets.  

The best known algorithm for computing the diameter (largest distance) of a graph is the naive algorithm of computing all-pairs 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 fine-grained 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 diameter. Thus, a useful preprocessing step is to add a set of edges (a hopset) to the graph that reduces the diameter of the graph, while preserving important distance information. I will present recent progress on bounds for hopsets.

See: https://theory.cs.rutgers.edu/theory_seminar