TY - GEN

T1 - Fredman's Trick Meets Dominance Product

T2 - 55th Annual ACM Symposium on Theory of Computing, STOC 2023

AU - Chan, Timothy M.

AU - Vassilevska Williams, Virginia

AU - Xu, Yinzhan

N1 - Publisher Copyright:
© 2023 Owner/Author.

PY - 2023/6/2

Y1 - 2023/6/2

N2 - 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 also 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.

AB - 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 also 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.

KW - fine-grained complexity

UR - http://www.scopus.com/inward/record.url?scp=85163110106&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85163110106&partnerID=8YFLogxK

U2 - 10.1145/3564246.3585237

DO - 10.1145/3564246.3585237

M3 - Conference contribution

AN - SCOPUS:85163110106

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 419

EP - 432

BT - STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing

A2 - Saha, Barna

A2 - Servedio, Rocco A.

PB - Association for Computing Machinery

Y2 - 20 June 2023 through 23 June 2023

ER -