Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV
Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV
复制标题
DOI：
10.1145/3519935.3520032
复制
发表时间：
2022-03
期刊：
影响因子：
--
通讯作者：
Timothy M. Chan;V. V. Williams-V.;Yinzhan Xu
中科院分区：
文献类型：
--
作者：
Timothy M. Chan;V. V. Williams-V.;Yinzhan Xu
3SUM假设、所有对最短路径（APSP）假设和强指数时间假设是细粒度复杂性领域的三个主要假设。到目前为止，在该领域内，前两个假设主要是关于Word RAM计算模型中的整数输入。“真实的APSP”和“真实的3SUM”假设断言APSP和3SUM假设在真实的RAM模型的合理版本中对实值输入成立，甚至比它们的整数对应物更可信。在非常可信的假设下，至少有一个是真的3SUM假说，SAPAPSP假说或SETH，Abboud，Vassilevska W。Yu [STOC 2015]证明了一个名为Triangle Collection的问题需要在n节点图上花费n3−o（1）时间。本文的主要结果是一个非平凡的下限略推广三角形集合，称为全彩色对三角形集合，在更可信的假设，即至少有一个真实的3 SUM，真实的APSP，和正交矢量（OV）的假设是真的。结合对三角形集合的先验约简的轻微修改，我们获得了多项式条件下界，例如（静态）ST最大流问题和动态版本的最大流，单源可达性计数和计数强连接组件，现在在新的较弱的假设下。我们的主要结果是建立在以下两条减少线。在第一行约简中，我们展示了全边稀疏三角形问题的真实的APSP和真实的3SUM硬度。以前的减少只从这些问题的整数变量。在第二行的减少，我们显示真实的APSP和OV硬度的一个变种的布尔矩阵乘法问题。沿着的方式，我们表明，三角形集合是等价于一个更简单的限制版本的问题，简化了以前的工作。我们的技术也有其他有趣的影响，如一个超线性的下限，基于真实的3SUM假设，和一个严格的下限的字符串匹配问题的OV假设的基础上，所有数字3SUM。
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.