Fri May 6, 3PM, Path, Matrix and Triangle Problems: algorithms and equivalences
Speaker: Virginia Vassilevska Williams , Berkeley
Date: May 6 2011
Time: 3:00PM to 4:00PM
Location: 2-132
Host: Michel Goemans
Contact: Michel Goemans, 3-2688, goemans@math.mit.edu
Abstract:
Many graph and matrix problems studied in optimization have relatively simple algorithms which run in time cubic in the number of vertices or rows. Some examples include matrix multiplication and all-pairs shortest paths. These problems have widespread applications, and developing more efficient algorithms for them would have a big impact. In 1969, Strassen gave a clever truly subcubic algorithm for matrix multiplication, and this insight has since lead to faster algorithms for many of the graph and matrix problems solvable in cubic time.
Nevertheless, several stubborn problems remain for which the best known running time is essentially cubic. The prototypical of these problems is all-pairs shortest paths. Other stubborn problems include the minimum weight cycle (girth) problem, the replacement paths problem, the second shortest simple path problem, and the simplest of them all, the problem of detecting a negative weight triangle in a graph. We have recently been able to show, perhaps surprisingly, that all these problems are equivalent, in the sense that if one has a truly subcubic algorithm, then all of them do. To accomplish this, we define a new, more refined notion of reduction, preserving "subcubicity" (the notion can easily be extended for any time exponent other than 3 as well).
One of our major goals is to develop a theory of equivalences between problems within P, analogous to that of NP-completeness. One reason P vs NP looks so hard to resolve is that many researchers from different areas have all been working on essentially the same (NP-complete) problem with no success. Our situation is entirely analogous: either these problems require essentially cubic time, or we are missing a fundamental insight which would make all of them simultaneously easier. In this talk I will give an overview of my results in the area, both algorithms and equivalences.
See other events that are part of
See other events happening in May 2011
