### 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

Abstract:

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