Hardness of Approximate Diameter: Now for Undirected Graphs

Hardness of Approximate Diameter: Now for Undirected Graphs

Abstract: Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in near-linear time.

A series of papers on fine-grained complexity have led to strong hardness results for diameter, culminating in our recent tradeoff curve in the upcoming FOCS'21 joint with Ray Li and Mina Dalirrooyfard, showing that under the Strong Exponential Time Hypothesis (SETH), for any integer k≥2 and δ>0, a 2−1/k−δ approximation for diameter in m-edge graphs requires mn^{1+1/(k−1)−o(1)} time. In particular, the simple linear time 2-approximation algorithm is optimal.

In this talk I will give an overview of the known algorithms and fine-grained lower bounds for diameter, including the SETH-based optimality of the 2-approximation algorithm.

Bio: Virginia Vassilevska Williams is the Steven and Renee Finn Career Development Associate Professor at MIT CSAIL and EECS. She obtained her Ph.D. from Carnegie Mellon University in 2008. After research and postdoctoral positions at the IAS in Princeton, UC Berkeley and Stanford, she spent 3.5 years as an assistant professor at Stanford University before joining MIT in early 2017. She is the recipient of an NSF CAREER award, a Google Faculty Research Award and an Alfred P. Sloan Research Fellowship, and in 2018 gave an invited lecture at the International Congress of Mathematicians.