Subcubic Equivalences Between Matrix, Path and Triangle Problems

by Anamay Tengse (School of Technology and Computer Science, TIFR)

Friday 15 Jul 2016, 16:00 → 17:30 Asia/Kolkata

A-201 (STCS Seminar Room)

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.