Title: Detecting, Finding and Minimizing Weighted Triangles

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