The All-Pairs Shortest Paths problem (APSP) is one of the most fundamental problems in algorithms research:
Given a graph with arbitrary (say, nonnegative) integer weights on its edges, compute the shortest paths distance between every pair of vertices.
Classical algorithms such as Floyd-Warshall solve APSP in O(n^3) time in n-node graphs. The fastest known algorithm by Williams'14 runs in n^3/exp(sqrt(log n)) time. One of the most tantalizing open problems in algorithms is whether an O(n^{3-eps}) time (so called truly subcubic) algorithm for APSP exists.
APSP is known to be runtime-equivalent to the so-called (min,+)-product of matrices: given two n by n matrices A and B, compute the n by n matrix C with entries C_{i,j}= min_k A_{i,k}+B_{k,j}. Over the last several decades, much research has gone into identifying structural properties of the input A and B for which C (and hence a version of APSP) can be computed in truly subcubic time. Practically all such approaches rely on the fact that matrix multiplication over the integers has a truly subcubic algorithm: n by n matrices can be multiplied in O~(n^\omega) time where \omega is known to be <2.372.
- Alon, Galil and Margalit (1997) showed that if both A and B have integer entries in {1,...,M}\cup {\infty}, then their (min,+)-product can be computed in O~(Mn^\omega) time
- Yuster (2009) showed that if at least one of A and B has integer entries in {1,...,M}\cup {\infty}, then their (min,+)-product can be computed in O~(Mn^{(3+\omega}/2) time
- Over the last decade more sufficient conditions for truly subcubic (min,+)-product have been uncovered: e.g. when A and/or B have a "bounded difference", "bounded monotonicity" or "blocked approximate-rank" property and when A and/or B have a small sublinear number of distinct values appearing in each row.
In this talk I'll focus on the third bullet, including the most general structural cases for which the (min,+)-product and APSP can be computed in truly subcubic time.
14/10/2025
When: Tuesday, October 14th, 12 PM - 1 PM
Where: Room 101 (Building D)
Virginia Vassilevska Williams is a Professor at MIT EECS and CSAIL. 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, an Alfred P. Sloan Research Fellowship, a 2023 Simons Investigator Award and a FOCS 2024 Test of Time Award. In 2018 she gave an invited lecture at the International Congress of Mathematicians.