UTCS Colloquia - Virginia Williams, Faculty Candidate, Stanford University, "Path problems, matrix products, algorithms, and equivalences" ACE 2.302

Contact Name: 
Kate Callard
ACES 2.302
Feb 28, 2013 11:00am - 12:00pm


Signup Schedule: http://apps.cs.utexas.edu/talkschedules/cgi/list_events.cgi

Talk Audience: UTCS Faculty, Grads, Undergrads, Other Interested Parties

Host: Vijaya Ramachandran 

Talk Abstract: The problem of computing shortest paths in a graph is old and fundamental. While computing the shortest path between two given vertices can be done efficiently, the best algorithms for computing the distances between all pairs of vertices, i.e. solving the all-pairs shortest paths problem (APSP), take essentially cubic time in the number of vertices. It is a major open problem whether APSP can be solved faster, or whether the cubic runtime is inherent. 

There are many problems related to APSP that were also not known to admit subcubic algorithms. These include finding the second shortest path between two vertices, finding the shortest cycle in a graph, and the all pairs bottleneck paths (APBP) problem which asks to compute, for all pairs of nodes, the path between them that maximizes the minimum edge weight. APBP seems intuitively more difficult than both the shortest cycle problem and the second shortest paths problem. Surprisingly, we show that APBP admits a truly subcubic algorithm, while shortest cycle and second shortest path (and several other path problems) are equivalent to APSP, so that if there is a subcubic algorithm for one of these problems, then all of them have subcubic algorithms. To prove the equivalences we develop a novel concept of truly subcubic reducibility. To obtain the improved algorithm for APBP, we reduce the problem to matrix multiplication, a problem with surprisingly fast algorithms that is often exploited in a black box fashion to solve other problems. Finally, we focus on the matrix multiplication problem itself ("opening up" the black box) and show how to improve over the Coppersmith-Winograd algorithm that had been the theoretically fastest way to multiply matrices for almost 25 years. This talk will aim to highlight the main ideas in this line of research.

Speaker Bio: Virginia Vassilevska Williams is a research associate at the computer science department at Stanford University and an assistant research engineer at the computer science division at UC Berkeley. She received her B.S. degree from the California Institute of Technology in 2003, double-majoring in mathematics and engineering and applied science (computer science). She got her Ph.D. in computer science from Carnegie Mellon University in 2008 under the guidance of Prof. Guy Blelloch. After graduating from Carnegie Mellon, she spent a year as a member of the Institute for Advanced Study in Princeton. From September 2009 until August 2011 she was a Computing Innovations Fellow at UC Berkeley, working with Prof. Satish Rao.