DIMACS Theoretical Computer Science Seminar

Title: Detecting, Finding and Minimizing Weighted Triangles

Speaker: Virginia Vassilevska, IAS

Date: Wednesday, April 15, 2009 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


We consider the problem of detecting particular types of triangles in a weighted graph. The weight of a triangle in a graph with weights on its edges and/or nodes is defined as the sum of the weights of the nodes and edges of the triangle. We focus on the problems of finding

 (1) a minimum weight triangle, 
 (2) a triangle of a prescribed weight ("exact triangle"), and 
 (3) a negative weight triangle. 
When the graph has weights only on its nodes, all these problems can be solved in matrix multiplication time. When the graph has edge weights, however, there are no known truly subcubic algorithms for any of these problems.

In this talk we will uncover surprising connections between these triangle problems, the all pairs shortest paths (APSP) problem, and the 3SUM problem. Our results indicate that obtaining fast algorithms for these triangle problems would result in a breakthrough in both APSP and 3SUM research.

Joint work with Ryan Williams