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.

翻译：3$SUM- Indexing 问题被引入为3$SUM问题的数据结构版本,目的是通过减少来证明静态数据结构的严格条件下限。 理想的情况是,3$SUM- Indexing的假设硬度应该被无条件的下限所取代。 不幸的是,我们远远没有证明这一点,最强的当前下限是来自STOC'20的Golovnev等人的对数查询时间较低。 此外,它们较低的约束线只对非适应性数据结构有效,它们明确要求对适应性数据结构采用较低的约束线。 我们的主要贡献恰恰是相对于适应性数据结构的制约范围较小。 作为次要结果,我们还加强了Golovnev等人的非适应性较低约束线,并通过一种我们发现本身很有意思的全新方法,证明对2美元位- probe非适应性3$SUM- Indexmination数据结构有很强的下限。