Subcubic Equivalences Between Path, Matrix, and Triangle Problems

by Virginia Vassilevska Williams and Ryan Williams

Oded's comments

Shiri presented one of the many (subcubic-time preserving) reductions in the paper: A reduction of matrix multiplication w.r.t $(+,\min)$ to deciding the existence of negative weight triangles in an edge-weigthed graph. This reduction can is composed of two main steps: (1) Finding a maximal set of $(1,2)$-edge disjoint negative triangles in tri-partite graphs is reduced to deciding the existence of negative triangles. (2) Matrix multiplication w.r.t $(+,\min)$ is reduced to a multiple-decision problem that refers to the existence negative triangles that use each of the possible $(1,2)$-edges in a tri-partite graph. Specifically, in (2) one performs, in parallel, multiple binary searches each designated to determine the value of a single entry in the product matrix. The binary search for location $(i,j)$ uses queries that refers to the $(1,2)$-edge $(i,j)$, where the answers to all these queries are collected from the multiple-decision problem. (Note that the multiple-decision problem is equivalent to finding a maximal set of $(1,2)$-edge disjoint negative triangles.)

The original abstract

See the FOCS'10 proceedings.

Back to list of Oded's choices.