Subcubic Equivalences Between Matrix, Path and Triangle Problems

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.