Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
复制标题
Fredman 的技巧与主导产品的结合：未加权 APSP、3SUM 计数等的细粒度复杂性
DOI：
10.1145/3564246.3585237
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Xu, Yinzhan
中科院分区：
文献类型：
--
作者：
Chan, Timothy M.;Vassilevska Williams, Virginia;Xu, Yinzhan
本文将Fredman的技巧[SICOMP‘76]和Matoušek的优势积方法[IPL’91]有机地结合起来，在边权在{1，2，…中的无向图的APSP的假设下，得到了关于细粒度复杂性的强有力的结果，n}需要n3−o(1)时间(当ω=2时)，我们给出了各种条件下界，包括未加权有向−的ann7/3−o(1)下界和计算两个n×n布尔矩阵之间的最小见证乘积的an2.2ωo(1)下界，即使=2时，也改进了它们的平凡下界。我们的方法也可以用来将非加权有向APSP问题归结为其他问题。特别地，我们证明了(当ω=2时)，如果未加权有向APP需要2.5−o(1)时间，则最小见证乘积需要n 7/3−o(1)时间。我们证明了，令人惊讶的是，许多细粒度复杂性的中心问题等价于它们的自然计数形式。特别地，我们证明了Min-Plus乘积和精确三角形与它们的计数形式次三次等价，3Sum与它的计数形式次二次等价；我们还利用加性组合学中Balog-Szemerédi-Gowers定理的新变体得到了新的算法。例如，我们得到了精确计算任意赋权图中最短路径数目的ANO(n3.83)时间确定性算法，改进了TextBook O(N4)时间算法。我们还得到了预处理论域中3Sum的快速算法和单调集上的3Sum的确定性算法，n}d。
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} requiresn3−o(1)time (when ω=2), we show a variety of conditional lower bounds, including ann7/3−o(1)lower bound for unweighted directed APSP and ann2.2−o(1)lower bound for computing the Minimum Witness Product between twon×nBoolean matrices, even if ω=2, improving upon their trivialn2lower 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 requiresn2.5−o(1)time, then Minimum Witness Product requiresn7/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 anO(n3.83) time deterministic algorithm for exactly counting the number of shortest paths in an arbitrary weighted graph, improving the textbookO(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.
登录
查看更多内容
更快的单调最小加产品、范围模式和单一来源替换路径
DOI：
--
发表时间：
2021
期刊：
and Programming (ICALP 2021
影响因子：
--
作者：
Gu, Yuzhou;Polak, Adam;Vassilevska Williams, Virginia;Xu, Yinzhan
通讯作者：
Xu, Yinzhan
适用于较少结构化矩阵的真正次三次最小加乘积及其应用
DOI：
--
发表时间：
2019
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
V. V. Williams;Yinzhan Xu
通讯作者：
Yinzhan Xu
针对所有对非递减路径问题的更快算法
DOI：
--
发表时间：
2019
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
Ran Duan;Ce Jin;Hongxun Wu
通讯作者：
Hongxun Wu
DOI：
--
发表时间：
2020
期刊：
Information Technology Convergence and Services
影响因子：
--
作者：
Andrea Lincoln;Adam Polak;V. V. Williams
通讯作者：
V. V. Williams
将 3SUM 简化为卷积 3SUM
DOI：
--
发表时间：
2020
期刊：
SIAM Symposium on Simplicity in Algorithms
影响因子：
--
作者：
Timothy M. Chan;Qizheng He
通讯作者：
Qizheng He