Events Calendar

CS Colloquium

Speaker: Virginia Vassilevska Williams, UC Berkeley

Talk Title: Path, matrix and triangle problems -- subcubic algorithms and equivalences

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.

Biography: Virginia Vassilevska Williams is currently a postdoctoral fellow working with Prof. Satish Rao, sponsored by a Computing Innovations Fellowship. She obtained her Bachelor's degree in mathematics and engineering and applied science from the California Institute of Technology in 2003. She completed her Ph.D. in computer science at Carnegie Mellon University in 2008 under the guidance of Prof. Guy Blelloch. She also spent a year as a postdoctoral member at the Institute for Advanced Study in Princeton, in Avi Wigderson's group. Her primary research interests are in graph algorithms and computational social choice.


Host: Prof. Ming-Deh Huang, USC

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: Kanak Agrawal