论文标题
取消基于3sum的降低中的添加结构
Removing Additive Structure in 3SUM-Based Reductions
论文作者
论文摘要
我们的工作探讨了$ 3 $总实例的硬度，而没有某些添加剂结构及其应用。作为我们的主要技术结果，我们表明，在尺寸 - $ n $整数集上解决$ 3 $ sum避免使用$ a+a+a+b = c+d $ for $ \ {a，b \} \ ne \ ne \ {c，d \} $仍然需要$ n^{2-o（1）} $ 3 $ 3 $ 3 $ 3 $ 3 $ 3 $ 3。这样的集合称为Sidon集，在加法组合学领域进行了充分研究。 - 结合以前的减少，这意味着全饰面稀疏的三角形问题在$ n $ -vertex上具有最高度$ $ \ sqrt {n} $，最多最多$ n^{k/2} $ n^{k/2} $ k $ -k $ -cycles每$ k \ ge 3 $ ge 3 $需要$ n^$ n^{2-o（1）$ nder，这可以用来通过Abboud，Bringmann，Khoury和Zamir [Stoc'22]加强先前的条件下限，分别为$ 4 $循环枚举，离线近似距离甲骨文和近似动态最短路径。 In particular, we show that no algorithm for the $4$-Cycle Enumeration problem on $n$-vertex $m$-edge graphs with $n^{o(1)}$ delays has $O(n^{2-\varepsilon})$ or $O(m^{4/3-\varepsilon})$ pre-processing time for $\varepsilon >0$.我们还通过对已知算法的简单修改，以$ 4 $循环检测来展示匹配的上限。 - 主要结果的略有概括也扩大了Dudek，Gawrychowski和Starikovskaya [Stoc'20]的结果，这是$ 3 $ 3 $ sum Hartnese of All norknyn norrivial 4-dldts的$ 3降低线性脱位测试（3-ldts）的$ 3 $ sugness：我们显示$ 3 $。 我们主要技术结果的证明结合了广泛的工具：balog-szemer {é} di-gowers定理，稀疏卷积算法和一个新的几乎是线性的哈希功能，以及几乎$ 3 $ umerviversal保证的整数保证，这些整数保证与没有小的线性关系。
Our work explores the hardness of $3$SUM instances without certain additive structures, and its applications. As our main technical result, we show that solving $3$SUM on a size-$n$ integer set that avoids solutions to $a+b=c+d$ for $\{a, b\} \ne \{c, d\}$ still requires $n^{2-o(1)}$ time, under the $3$SUM hypothesis. Such sets are called Sidon sets and are well-studied in the field of additive combinatorics. - Combined with previous reductions, this implies that the All-Edges Sparse Triangle problem on $n$-vertex graphs with maximum degree $\sqrt{n}$ and at most $n^{k/2}$ $k$-cycles for every $k \ge 3$ requires $n^{2-o(1)}$ time, under the $3$SUM hypothesis. This can be used to strengthen the previous conditional lower bounds by Abboud, Bringmann, Khoury, and Zamir [STOC'22] of $4$-Cycle Enumeration, Offline Approximate Distance Oracle and Approximate Dynamic Shortest Path. In particular, we show that no algorithm for the $4$-Cycle Enumeration problem on $n$-vertex $m$-edge graphs with $n^{o(1)}$ delays has $O(n^{2-\varepsilon})$ or $O(m^{4/3-\varepsilon})$ pre-processing time for $\varepsilon >0$. We also present a matching upper bound via simple modifications of the known algorithms for $4$-Cycle Detection. - A slight generalization of the main result also extends the result of Dudek, Gawrychowski, and Starikovskaya [STOC'20] on the $3$SUM hardness of nontrivial 3-Variate Linear Degeneracy Testing (3-LDTs): we show $3$SUM hardness for all nontrivial 4-LDTs. The proof of our main technical result combines a wide range of tools: Balog-Szemer{é}di-Gowers theorem, sparse convolution algorithm, and a new almost-linear hash function with almost $3$-universal guarantee for integers that do not have small-coefficient linear relations.
