TY - GEN
T1 - Simpler Reductions from Exact Triangle
AU - Chan, Timothy M.
AU - Xu, Yinzhan
N1 - Publisher Copyright:
Copyright © 2024 by SIAM.
PY - 2024
Y1 - 2024
N2 - 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 3SUM 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 3SUM 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 3SUM 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ătraşcu’s seminal work [STOC 2010]) were randomized.
AB - 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 3SUM 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 3SUM 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 3SUM 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ătraşcu’s seminal work [STOC 2010]) were randomized.
UR - http://www.scopus.com/inward/record.url?scp=85191281995&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85191281995&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85191281995
T3 - 2024 Symposium on Simplicity in Algorithms, SOSA 2024
SP - 28
EP - 38
BT - 2024 Symposium on Simplicity in Algorithms, SOSA 2024
A2 - Parter, Merav
A2 - Pettie, Seth
PB - Society for Industrial and Applied Mathematics Publications
T2 - 7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024
Y2 - 8 January 2024 through 10 January 2024
ER -