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

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 n 3-o(1) time (when ω = 2), we show a variety of conditional lower bounds, including an n 7/3-o(1) lower bound for unweighted directed APSP and an n 2.2-o(1) lower bound for computing the Minimum Witness Product between two n × n Boolean matrices, even if ω = 2, improving upon their trivial n 2 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 n 2.5-o(1) time, then Minimum Witness Product requires n 7/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(n 3.83 ) time deterministic algorithm for exactly counting the number of shortest paths in an arbitrary weighted graph, improving the textbook O(n 4 ) 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 .