  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.
