Simpler Reductions from Exact Triangle
Simpler Reductions from Exact Triangle
复制标题
精确三角形的更简单简化
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Yinzhan Xu
中科院分区：
文献类型：
--
作者：
Timothy M. Chan;Yinzhan Xu
在本文中，我们提供了从精确三角形到细粒度复杂性中两个重要问题的更简单的简化：具有少量零权重 4 美元循环的精确三角形和全边稀疏三角形。 Jin 和 Xu [STOC 2023] 考虑了具有少量零重量 $4$ 循环的精确三角形实例，他们将其用作中间问题来显示具有少量 4$ 循环的全边稀疏三角形的 $3$SUM 硬度（由 Abboud、Bringmann 和 Fischer [STOC 2023] 独立获得），该硬度进一步用于显示各种问题的 $3$SUM 硬度，包括$4$-循环枚举、离线近似距离预言机、动态近似最短路径和全节点最短循环。我们提供了从精确三角形到精确三角形的简单简化，并且具有一些零权重 4 美元循环。我们的新约简不仅简化了 Jin 和 Xu 之前的约简，而且还加强了条件下界，从 $3$SUM 假设到更可信的精确三角形假设。因此，Jin 和 Xu [STOC 2023] 以及 Abboud、Bringmann 和 Fischer [STOC 2023] 使用具有很少 4$ 循环的全边稀疏三角形作为中间问题显示的所有条件下界现在也适用于精确三角形假设。我们还提供了精确三角形假设下全边稀疏三角形问题的条件下界的两个替代证明，该证明最初由 Vassilevska Williams 和 Xu [FOCS 2020] 证明。我们的两种新简化都更简单，其中之一也是确定性的——之前从精确三角形或 3SUM 到全边稀疏三角形的所有简化（包括 P\u{a}tra\c{s}cu 的开创性工作 [STOC 2010]）都是随机的。
In this paper, we provide simpler reductions from Exact Triangle to two important problems in fine-grained complexity: Exact Triangle with Few Zero-Weight $4$-Cycles and All-Edges Sparse Triangle. Exact Triangle instances with few zero-weight $4$-cycles was considered by Jin and Xu [STOC 2023], who used it as an intermediate problem to show $3$SUM hardness of All-Edges Sparse Triangle with few $4$-cycles (independently obtained by Abboud, Bringmann and Fischer [STOC 2023]), which is further used to show $3$SUM hardness of a variety of problems, including $4$-Cycle Enumeration, Offline Approximate Distance Oracle, Dynamic Approximate Shortest Paths and All-Nodes Shortest Cycles. We provide a simple reduction from Exact Triangle to Exact Triangle with few zero-weight $4$-cycles. Our new reduction not only simplifies Jin and Xu's previous reduction, but also strengthens the conditional lower bounds from being under the $3$SUM hypothesis to the even more believable Exact Triangle hypothesis. As a result, all conditional lower bounds shown by Jin and Xu [STOC 2023] and by Abboud, Bringmann and Fischer [STOC 2023] using All-Edges Sparse Triangle with few $4$-cycles as an intermediate problem now also hold under the Exact Triangle hypothesis. We also provide two alternative proofs of the conditional lower bound of the All-Edges Sparse Triangle problem under the Exact Triangle hypothesis, which was originally proved by Vassilevska Williams and Xu [FOCS 2020]. Both of our new reductions are simpler, and one of them is also deterministic -- all previous reductions from Exact Triangle or 3SUM to All-Edges Sparse Triangle (including P\u{a}tra\c{s}cu's seminal work [STOC 2010]) were randomized.
Fredman 的技巧与主导产品的结合：未加权 APSP、3SUM 计数等的细粒度复杂性
DOI：
10.1145/3564246.3585237
发表时间：
2023
期刊：
Proc. 55th ACM Sympos. Theory of Computing (STOC
影响因子：
--
作者：
Chan, Timothy M.;Vassilevska Williams, Virginia;Xu, Yinzhan
通讯作者：
Xu, Yinzhan
DOI：
10.1145/3519935.3520032
发表时间：
2022-03
期刊：
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Timothy M. Chan;V. V. Williams-V.;Yinzhan Xu
通讯作者：
Timothy M. Chan;V. V. Williams-V.;Yinzhan Xu
通过短周期去除来近似 p 的硬度：周期检测、距离预言等等
DOI：
10.1145/3519935.3520066
发表时间：
2022
期刊：
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Abboud, Amir;Bringmann, Karl;Khoury, Seri;Zamir, Or
通讯作者：
Zamir, Or