[2203.09334] Stronger 3SUM-Indexing Lower Bounds
source link: https://arxiv.org/abs/2203.09334
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 17 Mar 2022 (v1), last revised 25 Oct 2022 (this version, v2)]
Stronger 3SUM-Indexing Lower Bounds
The 3SUM-Indexing problem was introduced as a data structure version of the 3SUM problem, with the goal of proving strong conditional lower bounds for static data structures via reductions. Ideally, the conjectured hardness of 3SUM-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 3SUM-Indexing data structures via a completely new approach that we find interesting in its own right.
| Comments: | To be published in SODA2023 |
| Subjects: | Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC) |
| MSC classes: | 68P05 |
| ACM classes: | E.1; F.2.0 |
| Cite as: | arXiv:2203.09334 [cs.DS] |
| (or arXiv:2203.09334v2 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2203.09334 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK