Virginia V. Williams colloquium, 02/17, 3:30
David Kempe
our next theory talk is another faculty candidate: Virginia
Vassilevska Williams. All the important details about her talk are
below. I'm looking forward to seeing many of you there.
Speaker: Virginia Vassilevska Williams, UC Berkeley
Time: Thursday, 02/17, 3:30pm
Location: SSL 150
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.
Bio:
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.