Tata Institute of Fundamental Research
Subcubic Equivalences Between Matrix, Path and Triangle Problems
STCS Student Seminar
Speaker:
Anamay Tengse
Organiser:
Nikhil S Mande
Date:
Friday, 15 Jul 2016, 16:00 to 17:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Anamay Tengse |
| Organiser: | Nikhil S Mande |
| Date: | Friday, 15 Jul 2016, 16:00 to 17:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
- 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.