论文标题
通过添加剂组合制剂，更强的3-和下限对于大约距离甲骨文
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics
论文作者
论文摘要
最近，“短周期去除”技术是由Abboud，Bringmann，Khoury和Zamir（Stoc '22）引入的，以证明近似的细粒度硬度。它的主要技术结果是，在$ n^{1/2} $中列出所有三角形 - 常规图为$ n^{2-o（1）} $ - 即使短周期的数量很小，在3-sum猜想下很难;也就是说，当$ k $ -cycles的数量为$ o（n^{k/2+γ}）$，对于$γ<1/2 $。 Abboud等。通过在图表上应用结构与随机性参数来实现$γ\ geq 1/4 $。在本文中，我们退后一步，在3-SUM问题的数量上应用概念上的类似论点。因此，我们实现了最好的$γ= 0 $，以及3-sum猜想下的以下下限： *近似距离甲骨文：开创性的Thorup-Zwick距离牙齿座伸展$ 2K \ pm o（1）$（在预处理图中$ O（m n^{1/k}）$ time之后。在同样的时间里，假设查询时间为$ n^{o（1）} $ abboud等。证明了$ω（m^{1+ \ frac {1} {12.7552 \ cdot k}}）$在预处理时间上的下限；我们将其提高到$ω（m^{1+ \ frac1 {2k}}）$，距离上限仅是一个因子2。我们还获得了$ 2+o（1）$和$3-ε$的紧密界限和动态最短路径的更高下限。 *列表4循环：Abboud等。证明了第一个用于列出图中所有4个循环的超级线性下限，排除$（m^{1.1927}+t）^{1+o（1）} $ time算法，其中$ t $是4个循环的数量。我们通过表明$ \ widetilde {o}（\ min（m^{4/3}，n^2），n^2） +t）$上限紧密至$ n^{o（1）} $ castor来解决这个基本问题的复杂性。 我们的结果利用了来自添加剂组合学的丰富工具，最著名的是Balog-Szemerédi-Gowers定理和Rusza覆盖的引理。如果其中一组的加倍，则可能具有独立感兴趣的关键成分是3-SUM的次级算法。
The "short cycle removal" technique was recently introduced by Abboud, Bringmann, Khoury and Zamir (STOC '22) to prove fine-grained hardness of approximation. Its main technical result is that listing all triangles in an $n^{1/2}$-regular graph is $n^{2-o(1)}$-hard under the 3-SUM conjecture even when the number of short cycles is small; namely, when the number of $k$-cycles is $O(n^{k/2+γ})$ for $γ<1/2$. Abboud et al. achieve $γ\geq 1/4$ by applying structure vs. randomness arguments on graphs. In this paper, we take a step back and apply conceptually similar arguments on the numbers of the 3-SUM problem. Consequently, we achieve the best possible $γ=0$ and the following lower bounds under the 3-SUM conjecture: * Approximate distance oracles: The seminal Thorup-Zwick distance oracles achieve stretch $2k\pm O(1)$ after preprocessing a graph in $O(m n^{1/k})$ time. For the same stretch, and assuming the query time is $n^{o(1)}$ Abboud et al. proved an $Ω(m^{1+\frac{1}{12.7552 \cdot k}})$ lower bound on the preprocessing time; we improve it to $Ω(m^{1+\frac1{2k}})$ which is only a factor 2 away from the upper bound. We also obtain tight bounds for stretch $2+o(1)$ and $3-ε$ and higher lower bounds for dynamic shortest paths. * Listing 4-cycles: Abboud et al. proved the first super-linear lower bound for listing all 4-cycles in a graph, ruling out $(m^{1.1927}+t)^{1+o(1)}$ time algorithms where $t$ is the number of 4-cycles. We settle the complexity of this basic problem by showing that the $\widetilde{O}(\min(m^{4/3},n^2) +t)$ upper bound is tight up to $n^{o(1)}$ factors. Our results exploit a rich tool set from additive combinatorics, most notably the Balog-Szemerédi-Gowers theorem and Rusza's covering lemma. A key ingredient that may be of independent interest is a subquadratic algorithm for 3-SUM if one of the sets has small doubling.
