Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More

Oded's comments

Rather than highlighting (in the title) a common technical aspect of the proofs, I would have highlighted (as done in the introduction) a common conceptual theme of the results. Specifically, the results address questions regarding the sensitivity of (fine-grained) complexity to variants such as directed vs undirected, fixed order vs none, and counting vs deciding. More specifically, the results include

• Evidence that (unweighted) directed APSP may be harder than (unweighted) undirected APSP, provided that $\omega$ is smaller than $7/3$ and even if $\omega=2$. (Recall that $\omega$ is known to be smaller than 2.373.) The evidence relies on the hypothesis that APSP in weighted $n$-vertex graphs with weights in $[n]$ requires $n^{3-o(1)}$ time.
• Evidence that finding the minimum-index intermediate vertices in 2-paths (i.e., Min-Withness-Prod) may be harder than finding arbitrary intermediate vertices (BMM), provided that $\omega$ is smaller than $11/5$ and even if $\omega=2$. The evidence relies on the same hypothesis as above (but a stronger result holds under a stronger hypothesis).
• Fine-grainly reducing several counting problems (e.g., for 3SUM) to their decisional version (see Sec 1.3).
  Amir actually called by attention to this work because of this reduction, pointing out that, for adequare threshold of few-vs-many, instances with few solutions can be handled in a rather starightforward manner whereas instances with many solutions are shown to structure that fascilites counting.
  In addition, for weighted APSP, while not providing a fine-grained reduction, the paper does provide a first significant improvement for the counting problem (see Sec 5.4).

The original abstract

In this paper we carefully combine Fredman's trick [SICOMP'76] and Matou?ek's approach for dominance product [IPL'91] to obtain powerful results in fine-grained complexity:

• Under the hypothesis that APSP for undirected graphs with edge weights in {1,2,…,n} requires n3?o(1) time (when ?=2), we show a variety of conditional lower bounds, including an n7/3?o(1) lower bound for unweighted directed APSP and an n2.2?o(1) lower bound for computing the Minimum Witness Product between two nªn Boolean matrices, even if ?=2, improving upon their trivial n2 lower bounds. Our techniques can also be used to reduce the unweighted directed APSP problem to other problems. In particular, we show that (when ?=2), if unweighted directed APSP requires n2.5?o(1) time, then Minimum Witness Product requires n7/3?o(1) time.
• We show that, surprisingly, many central problems in fine-grained complexity are equivalent to their natural counting versions. In particular, we show that Min-Plus Product and Exact Triangle are subcubically equivalent to their counting versions, and 3SUM is subquadratically equivalent to its counting version.
• We obtain new algorithms using new variants of the Balog-Szemer?di-Gowers theorem from additive combinatorics. For example, we get an O(n3.83) time deterministic algorithm for exactly counting the number of shortest paths in an arbitrary weighted graph, improving the textbook O˜(n4) time algorithm. We also get faster algorithms for 3SUM in preprocessed universes, and deterministic algorithms for 3SUM on monotone sets in {1,2,…,n}d.

See arxiv 2303.14572.