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)

- 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.