Approximating the Diameter of a Graph

I will talk about algorithms and conditional lower bounds for approximating the diameter of a graph (the largest distance between two vertices). The best known algorithm for exactly computing the diameter of a graph is the naive algorithm of computing all-pairs shortest paths (APSP) and taking the largest distance. Furthermore, no significantly better algorithm exists under the Strong Exponential Time Hypothesis. Running APSP can be prohibitively slow for very large graphs, so we seek much faster algorithms that produce an approximation of the diameter. I will discuss the landscape of time vs. accuracy trade-off algorithms and hardness for diameter.