SPEAKER: Virginia Vassilevska TIME: Wednesday 12-1pm, November 8, 2006 PLACE: NSH 1507 TITLE: A dominance approach to weighted graph problems ABSTRACT: Fast matrix multiplication allows us to obtain faster algorithms for many graph problems. A notable example is that of detecting a triangle in a graph - the naiive algorithm runs in O(n^3), while cubing the adjacency matrix gives an O(n^2.38) algorithm. Other problems that have benefitted from fast matrix multiplication include graph perfect matching, unweighted APSP, linear programming. Most of these problems are unweighted, and it is unclear how to apply the matrix multiplication techniques to their weighted counterparts. We show how to use a different kind of matrix product, the dominance product, to solve some weighted problems such as finding a maximum weighted triangle in a graph, computing bits of the distance product and finding the bottleneck distances between all pairs of vertices.