"Approximating graph diameter: algorithms, hardness, and hardness of hardness"
Ray Li (Stanford)
Monday, October 4th 2021, 2-3pm
Abstract:
Computing the diameter of a graph (the maximum shortest path distance) is an important theoretical and practical question. The best known exact algorithms compute the distance between every pair of vertices. Faster approximation algorithms are known. A natural question is whether the known algorithms and approximations are the best possible, and recent fine grained complexity work gives some answers. I will survey the landscape of approximating the diameter, which includes algorithms, hardness (of approximation) results (based on SETH, the Strong Exponential Time Hypothesis), and "hardness of hardness of approximation" results (based on another hypothesis, NSETH).
Based in part on joint work with Mina Dalirrooyfard and Virginia Vassilevska Williams.