  One of the main hypotheses in fine-grained complexity is that All-Pairs
Shortest Paths (APSP) for $n$-node graphs requires $n^{3-o(1)}$ time. Another
famous hypothesis is that the $3$SUM problem for $n$ integers requires
$n^{2-o(1)}$ time. Although there are no direct reductions between $3$SUM and
APSP, it is known that they are related: there is a problem,
$(\min,+)$-convolution that reduces in a fine-grained way to both, and a
problem Exact Triangle that both fine-grained reduce to.
  In this paper we find more relationships between these two problems and other
basic problems. P\u{a}tra\c{s}cu had shown that under the $3$SUM hypothesis the
All-Edges Sparse Triangle problem in $m$-edge graphs requires $m^{4/3-o(1)}$
time. The latter problem asks to determine for every edge $e$, whether $e$ is
in a triangle. It is equivalent to the problem of listing $m$ triangles in an
$m$-edge graph where $m=\tilde{O}(n^{1.5})$, and can be solved in $O(m^{1.41})$
time [Alon et al.'97] with the current matrix multiplication bounds, and in
$\tilde{O}(m^{4/3})$ time if $\omega=2$.
  We show that one can reduce Exact Triangle to All-Edges Sparse Triangle,
showing that All-Edges Sparse Triangle (and hence Triangle Listing) requires
$m^{4/3-o(1)}$ time also assuming the APSP hypothesis. This allows us to
provide APSP-hardness for many dynamic problems that were previously known to
be hard under the $3$SUM hypothesis.
  We also consider the previously studied All-Edges Monochromatic Triangle
problem. Via work of [Lincoln et al.'20], our result on All-Edges Sparse
Triangle implies that if the All-Edges Monochromatic Triangle problem has an
$O(n^{2.5-\epsilon})$ time algorithm for $\epsilon>0$, then both the APSP and
$3$SUM hypotheses are false. We also connect the problem to other
``intermediate'' problems, whose runtimes are between $O(n^\omega)$ and
$O(n^3)$, such as the Max-Min product problem.

Computational Complexity