论文标题
更强的3sum索引下限
Stronger 3SUM-Indexing Lower Bounds
论文作者
论文摘要
$ 3 $汇总问题是作为$ 3 $总问题的数据结构版本引入的，目的是通过减少证明静态数据结构的有条件下限。理想情况下，$ 3 $汇总的猜想硬度应由无条件的下限代替。不幸的是，我们远未证明这一点，最强的电流下限是Golovnev等人的对数查询时间下限。来自stoc'20。此外，它们的下限仅适用于非自适应数据结构，他们明确要求为自适应数据结构提供下限。我们的主要贡献正是针对自适应数据结构的下限。作为次要结果，我们还加强了Golovnev等人的非自适应下限。并通过一种全新的方法证明了强大的下限，以$ 2 $ bit-bit-bit-probe $ 3 $ sum-ride-Indexing数据结构，我们本身就发现了有趣的。
The $3$SUM-Indexing problem was introduced as a data structure version of the $3$SUM problem, with the goal of proving strong conditional lower bounds for static data structures via reductions. Ideally, the conjectured hardness of $3$SUM-Indexing should be replaced by an unconditional lower bound. Unfortunately, we are far from proving this, with the strongest current lower bound being a logarithmic query time lower bound by Golovnev et al. from STOC'20. Moreover, their lower bound holds only for non-adaptive data structures and they explicitly asked for a lower bound for adaptive data structures. Our main contribution is precisely such a lower bound against adaptive data structures. As a secondary result, we also strengthen the non-adaptive lower bound of Golovnev et al. and prove strong lower bounds for $2$-bit-probe non-adaptive $3$SUM-Indexing data structures via a completely new approach that we find interesting in its own right.
