In this talk, we will discuss subcubic equivalence between the following problems:
- Finding the distance product of matrices
- Directed all pairs shortest paths
- Undirected all pairs shortest paths
- Replacement paths
- Second shortest simple path
- Detecting a triangle with negative total weight
All the above mentioned problems have cubic time algorithm, but neither a cubic lower bound nor a subcubic time algorithm is known for any of them. The equivalence shows that either all or none of them have a subcubic algorithm.
These equivalences appear as a part of the 2010 FOCS paper by Virginia Williams and Ryan Williams.
We will begin by formalizing the notion of subcubic equivalence and the distance product of matrices.
Note: These are the equivalences that were not covered during the qualifiers. But we will be covering the required basics again.
