Virginia Vassilevska Williams, CSE Faculty Candidate

Dr. Williams is a Postdoctoral Scholar at the University of California, Berkeley.

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

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