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