TY - GEN
T1 - Hardness for triangle problems under even more believable hypotheses
T2 - 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022
AU - Chan, Timothy M.
AU - Williams, Virginia Vassilevska
AU - Xu, Yinzhan
N1 - \u2217The full version of this paper is available at https://arxiv.org/abs/2203.08356. \u2020Supported by NSF Grant CCF-1814026. \u2021Supported by NSF Grants CCF-2129139 and CCF-1909429, a BSF Grant BSF:2020356, a Google Research Fellowship and a Sloan Research Fellowship. \u00A7Partially supported by NSF Grant CCF-2129139.
PY - 2022/9/6
Y1 - 2022/9/6
N2 - The 3SUM hypothesis, the All-Pairs Shortest Paths (APSP) hypothesis and the Strong Exponential Time Hypothesis are the three main hypotheses in the area of fine-grained complexity. So far, within the area, the first two hypotheses have mainly been about integer inputs in the Word RAM model of computation. The "Real APSP"and "Real 3SUM"hypotheses, which assert that the APSP and 3SUM hypotheses hold for real-valued inputs in a reasonable version of the Real RAM model, are even more believable than their integer counterparts. Under the very believable hypothesis that at least one of the Integer 3SUM hypothesis, Integer APSP hypothesis or SETH is true, Abboud, Vassilevska W. and Yu [STOC 2015] showed that a problem called Triangle Collection requires n3-o(1) time on an n-node graph. The main result of this paper is a nontrivial lower bound for a slight generalization of Triangle Collection, called All-Color-Pairs Triangle Collection, under the even more believable hypothesis that at least one of the Real 3SUM, the Real APSP, and the Orthogonal Vector (OV) hypotheses is true. Combined with slight modifications of prior reductions from Triangle Collection, we obtain polynomial conditional lower bounds for problems such as the (static) ST-Max Flow problem and dynamic versions of Max Flow, Single-Source Reachability Count, and Counting Strongly Connected Components, now under the new weaker hypothesis. Our main result is built on the following two lines of reductions. In the first line of reductions, we show Real APSP and Real 3SUM hardness for the All-Edges Sparse Triangle problem. Prior reductions only worked from the integer variants of these problems. In the second line of reductions, we show Real APSP and OV hardness for a variant of the Boolean Matrix Multiplication problem. Along the way we show that Triangle Collection is equivalent to a simpler restricted version of the problem, simplifying prior work. Our techniques also have other interesting implications, such as a super-linear lower bound of Integer All-Numbers 3SUM based on the Real 3SUM hypothesis, and a tight lower bound for a string matching problem based on the OV hypothesis.
AB - The 3SUM hypothesis, the All-Pairs Shortest Paths (APSP) hypothesis and the Strong Exponential Time Hypothesis are the three main hypotheses in the area of fine-grained complexity. So far, within the area, the first two hypotheses have mainly been about integer inputs in the Word RAM model of computation. The "Real APSP"and "Real 3SUM"hypotheses, which assert that the APSP and 3SUM hypotheses hold for real-valued inputs in a reasonable version of the Real RAM model, are even more believable than their integer counterparts. Under the very believable hypothesis that at least one of the Integer 3SUM hypothesis, Integer APSP hypothesis or SETH is true, Abboud, Vassilevska W. and Yu [STOC 2015] showed that a problem called Triangle Collection requires n3-o(1) time on an n-node graph. The main result of this paper is a nontrivial lower bound for a slight generalization of Triangle Collection, called All-Color-Pairs Triangle Collection, under the even more believable hypothesis that at least one of the Real 3SUM, the Real APSP, and the Orthogonal Vector (OV) hypotheses is true. Combined with slight modifications of prior reductions from Triangle Collection, we obtain polynomial conditional lower bounds for problems such as the (static) ST-Max Flow problem and dynamic versions of Max Flow, Single-Source Reachability Count, and Counting Strongly Connected Components, now under the new weaker hypothesis. Our main result is built on the following two lines of reductions. In the first line of reductions, we show Real APSP and Real 3SUM hardness for the All-Edges Sparse Triangle problem. Prior reductions only worked from the integer variants of these problems. In the second line of reductions, we show Real APSP and OV hardness for a variant of the Boolean Matrix Multiplication problem. Along the way we show that Triangle Collection is equivalent to a simpler restricted version of the problem, simplifying prior work. Our techniques also have other interesting implications, such as a super-linear lower bound of Integer All-Numbers 3SUM based on the Real 3SUM hypothesis, and a tight lower bound for a string matching problem based on the OV hypothesis.
KW - fine-grained complexity
UR - http://www.scopus.com/inward/record.url?scp=85132749113&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85132749113&partnerID=8YFLogxK
U2 - 10.1145/3519935.3520032
DO - 10.1145/3519935.3520032
M3 - Conference contribution
AN - SCOPUS:85132749113
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1501
EP - 1514
BT - STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Leonardi, Stefano
A2 - Gupta, Anupam
PB - Association for Computing Machinery
Y2 - 20 June 2022 through 24 June 2022
ER -