2025-11-12T12:22:13.745054

3SUM in Preprocessed Universes: Faster and Simpler

Kasliwal, Polak, Sharma
We revisit the 3SUM problem in the \emph{preprocessed universes} setting. We present an algorithm that, given three sets $A$, $B$, $C$ of $n$ integers, preprocesses them in quadratic time, so that given any subsets $A' \subseteq A$, $B' \subseteq B$, $C' \subseteq C$, it can decide if there exist $a \in A'$, $b \in B'$, $c \in C'$ with $a+b=c$ in time $O(n^{1.5} \log n)$. In contrast to both the first subquadratic $\tilde{O}(n^{13/7})$-time algorithm by Chan and Lewenstein (STOC 2015) and the current fastest $\tilde{O}(n^{11/6})$-time algorithm by Chan, Vassilevska Williams, and Xu (STOC 2023), which are based on the Balog--Szemerédi--Gowers theorem from additive combinatorics, our algorithm uses only standard 3SUM-related techniques, namely FFT and linear hashing modulo a prime. It is therefore not only faster but also simpler. Just as the two previous algorithms, ours not only decides if there is a single 3SUM solution but it actually determines for each $c \in C'$ if there is a solution containing it. We also modify the algorithm to still work in the scenario where the set $C$ is unknown at the time of preprocessing. Finally, even though the simplest version of our algorithm is randomized, we show how to make it deterministic losing only polylogarithmic factors in the running time.
academic

3SUM in Preprocessed Universes: Faster and Simpler

基本信息

  • 论文ID: 2410.16784
  • 标题: 3SUM in Preprocessed Universes: Faster and Simpler
  • 作者: Shashwat Kasliwal (IIT Delhi), Adam Polak (Bocconi University), Pratyush Sharma (IIT Delhi)
  • 分类: cs.DS (数据结构与算法)
  • 发表时间/会议: TheoretiCS Volume 4 (2025), Article 24 (Invited article from SOSA 2025)
  • 论文链接: https://arxiv.org/abs/2410.16784

摘要

本文重新审视了预处理宇宙设定下的3SUM问题。提出了一个算法，给定三个包含n个整数的集合A、B、C，在二次时间内对其进行预处理，使得对于任意子集A' ⊆ A、B' ⊆ B、C' ⊆ C，能够在O(n^1.5 log n)时间内判断是否存在a ∈ A'、b ∈ B'、c ∈ C'使得a+b=c。相比于Chan和Lewenstein的首个次二次O(n^13/7)算法和Chan等人当前最快的O(n^11/6)算法（基于加法组合数学的Balog-Szemerédi-Gowers定理），本文算法仅使用标准的3SUM相关技术（FFT和模质数线性哈希），因此不仅更快而且更简单。

研究背景与动机

问题背景

3SUM问题是细粒度复杂性理论中的三个核心问题之一（与APSP和SAT并列）。给定三个包含n个整数的集合A、B、C，需要判断是否存在三元组(a,b,c) ∈ A × B × C使得a + b = c。标准教科书方法的时间复杂度为O(n²)，最快已知算法仅提供log²n/(log log n)²的改进。

研究动机

  1. 复杂性理论意义：普遍猜测不存在时间复杂度为O(n^(2-ε))的3SUM算法，许多问题的条件下界都基于此假设
  2. 变体研究价值：研究确实存在强次二次算法的3SUM变体有助于更好理解3SUM的复杂性
  3. 实用性考虑：预处理宇宙变体在实际应用中具有重要价值，允许对多个查询进行高效处理

现有方法局限性

  • Chan-Lewenstein算法：基于复杂的Balog-Szemerédi-Gowers定理，实现困难
  • Chan-Vassilevska Williams-Xu算法：虽然更快但仍依赖高深的加法组合数学理论
  • 两者都缺乏简单性，实际实现复杂度高

核心贡献

  1. 算法效率提升：提出了查询时间为O(n^1.5 log n)的算法，显著优于之前的O(n^11/6)
  2. 技术简化：仅使用FFT和线性哈希等标准技术，避免复杂的加法组合数学工具
  3. 功能完整性：不仅判断是否存在解，还能确定每个c ∈ C'是否参与某个解
  4. 场景扩展：处理集合C在预处理时未知的情况
  5. 确定性版本：提供确定性算法，仅损失多对数因子

方法详解

任务定义

输入：三个包含n个整数的集合A、B、C 预处理：在O(n²)时间内预处理这些集合 查询：给定子集A' ⊆ A、B' ⊆ B、C' ⊆ C，在O(n^1.5 log n)时间内判断对每个c ∈ C'是否存在a ∈ A'、b ∈ B'使得a + b = c

核心算法架构

已知集合C的随机化算法（定理3.1）

预处理阶段：

  1. 从区间[n^1.5, 2n^1.5)中均匀随机选择质数p
  2. 计算假阳性集合：B := {(a,b,c) ∈ A × B × C : a + b ≡ c (mod p) ∧ a + b ≠ c}
  3. 期望假阳性数量：E|B| ≤ O(n^1.5 log n)

查询阶段：

  1. 使用FFT在O(p log p)时间内计算(A' + B') mod p的多重集
  2. 创建哈希表H，存储每个c ∈ C'的模p解数量
  3. 遍历假阳性集合B，减去当前实例中的假阳性
  4. 对每个c ∈ C'，若Hc > 0则答"是"，否则答"否"

未知集合C的算法（定理4.1）

预处理阶段：

  1. 计算和集A + B
  2. 对每个x ∈ A + B，存储见证集Wx := {(a,b) ∈ A × B : a + b = x}
  3. 选择随机质数m ∈ [n^1.5, 2·n^1.5)
  4. 对每个余数r ∈ m，准备列表Lr := {x ∈ A + B : x ≡ r (mod m)}

查询阶段：

  1. 使用FFT计算(A' + B') mod m
  2. 对每个c ∈ C'：
    • 检查c是否在A + B中
    • 使用恒等式计算真实解数量：模m解数量减去假阳性数量
    • 通过遍历Lc mod m中x ≠ c的元素计算假阳性

技术创新点

  1. 哈希技术的巧妙运用：通过选择适当大小的质数模数，平衡FFT效率和假阳性数量
  2. 假阳性控制：利用引理2.2控制假阳性期望数量为O(n^1.5 log n)
  3. FFT优化：将3SUM问题转化为多项式乘法，利用FFT的O(m log m)复杂度
  4. 确定性转换：使用多个模数的组合策略实现确定性版本

实验设置

理论分析框架

本文主要进行理论分析，采用标准的细粒度复杂性分析方法：

计算模型：

  • 标准字RAM模型，O(log n)位字长
  • 输入数字界限为n^O(1)
  • 算术操作常数时间

复杂度分析：

  • 时间复杂度：预处理O(n²)，查询O(n^1.5 log n)
  • 空间复杂度：已知C版本O(n^1.5 log n)，未知C版本O(n²)
  • 随机性：Las Vegas算法（期望时间界限）

对比基准

  1. Chan-Lewenstein (STOC 2015)：O(n^13/7)查询时间
  2. Chan-Vassilevska Williams-Xu (STOC 2023)：O(n^11/6)查询时间
  3. 标准3SUM算法：O(n²)时间（无预处理）

实验结果

复杂度对比分析

算法预处理时间查询时间空间复杂度确定性
Chan-LewensteinO(n²)O(n^13/7) ≈ O(n^1.857)O(n^13/7)需O(n^ω)预处理
Chan等人O(n²)O(n^11/6) ≈ O(n^1.833)O(n² log n)查询时间O(n^1.891)
本文（已知C）O(n²)O(n^1.5 log n)O(n^1.5 log n)损失多对数因子
本文（未知C）O(n²)O(n^1.5 log n)O(n²)定理5.1

性能提升量化

  • 查询时间改进：从O(n^11/6) ≈ O(n^1.833)提升至O(n^1.5)，指数降低约0.333
  • 实现复杂度：避免Balog-Szemerédi-Gowers定理，仅需FFT和哈希
  • 功能完整性：保持All-Numbers 3SUM能力

算法正确性

通过严格的概率分析证明：

  • 假阳性期望界限：E|B| ≤ O(n^1.5 log n)（引理2.2）
  • Las Vegas性质：通过重启机制保证确定的运行时间界限
  • 完备性：所有真实解都被正确识别

相关工作

3SUM问题研究脉络

  1. 经典3SUM：Gajentaan-Overmars引入，O(n²)标准算法
  2. 轻微改进：Baran-Demaine-Pătraşcu实现polylog因子改进
  3. 变体研究：
    • 小宇宙3SUM：FFT方法，O(n + U log U)时间
    • 3SUM索引：不同的预处理模式
    • 实数RAM版本：Fischer等人的适配工作

预处理宇宙研究

  • Bansal-Williams：首次提出预处理宇宙概念
  • Chan-Lewenstein：首个次二次算法，基于BSG定理
  • Chan等人：当前最快算法，直接证明BSG推论

技术工具发展

  • FFT在3SUM中的应用：小宇宙情况下的经典方法
  • 线性哈希：假阳性控制的标准技术
  • 确定性技术：Fischer-Kaliciak-Polak的去随机化工具

结论与讨论

主要结论

  1. 效率突破：实现了O(n^1.5 log n)查询时间，显著优于之前最好结果
  2. 简化成功：避免复杂的加法组合数学，仅使用基础工具
  3. 实用性增强：提供确定性版本和未知C场景的处理方案

局限性分析

  1. 空间复杂度：未知C版本需要O(n²)空间存储完整和集
  2. 模型限制：假设输入数字有界，实际应用可能需要额外处理
  3. 实数RAM：尚不清楚能否适配到实数RAM模型
  4. 常数因子：理论分析未考虑实际实现的常数开销

未来研究方向

  1. 实数RAM适配：探索在实数RAM模型中的可行性
  2. 空间优化：减少未知C场景的空间需求
  3. 下界研究：探索预处理宇宙3SUM的理论下界
  4. 实际实现：开发高效的实际算法实现

深度评价

优点

  1. 理论贡献显著：查询时间从O(n^1.833)改进到O(n^1.5)，提升幅度大
  2. 技术创新巧妙：
    • 质数选择策略平衡FFT效率和假阳性控制
    • 确定性转换的多模数方法具有普适性
  3. 实用价值高：算法简单易实现，避免复杂的组合数学工具
  4. 分析严谨：概率分析和复杂度证明完整可靠
  5. 写作清晰：技术描述准确，算法描述易于理解

不足

  1. 创新程度：主要是已有技术的巧妙组合，原创性相对有限
  2. 实验验证缺失：纯理论工作，缺乏实际性能测试
  3. 适用范围：
    • 输入数字有界假设在实际中可能过强
    • 实数RAM适配性未知
  4. 空间效率：未知C版本的O(n²)空间需求可能限制实际应用

影响力评估

  1. 学术价值：为细粒度复杂性理论提供新的技术路径
  2. 实用潜力：简化的算法更容易在实际系统中部署
  3. 启发意义：证明了标准技术组合可以超越复杂理论工具
  4. 后续研究：可能启发其他几何/组合问题的类似改进

适用场景

  1. 数据库查询：大规模数据集的三元组查询优化
  2. 计算几何：相关几何问题的预处理加速
  3. 密码学应用：某些基于3SUM困难性的协议优化
  4. 算法竞赛：实际编程竞赛中的高效实现

参考文献

论文引用了16篇相关工作，主要包括：

  • 3 Baran, Demaine, Pătraşcu: 经典3SUM改进
  • 5 Chan, Lewenstein: 首个预处理宇宙次二次算法
  • 6 Chan, Vassilevska Williams, Xu: 当前最快算法
  • 8 Fischer, Kaliciak, Polak: 确定性3SUM技术
  • 16 Vassilevska Williams: 细粒度复杂性综述

总体评价：这是一篇高质量的理论计算机科学论文，在3SUM问题的预处理宇宙变体上取得了显著的理论突破。虽然技术创新相对增量式，但其简化复杂算法并提升性能的贡献具有重要价值。论文的理论分析严谨，写作清晰，为相关领域提供了有价值的新工具和洞察。