2026-09-08T01:21:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26467 2026-09-05T19:44:23Z ddc:004 open_access

Improved Time-Space Tradeoffs for 3SUM-Indexing Dinur, Itai Golovnev, Alexander Data Structures 3SUM Function Inversion 3SUM-Indexing is a preprocessing variant of the 3SUM problem that has recently received a lot of attention. The best known time-space tradeoff for the problem is T S³ = n⁶ (up to logarithmic factors), where n is the number of input integers, S is the length of the preprocessed data structure, and T is the running time of the query algorithm. This tradeoff was achieved in [Kopelowitz and Porat, 2019; Golovnev et al., 2020] using the Fiat-Naor generic algorithm for Function Inversion. Consequently, [Golovnev et al., 2020] asked whether this algorithm can be improved by leveraging the structure of 3SUM-Indexing. In this paper, we exploit the structure of 3SUM-Indexing to give a time-space tradeoff of T S = n^{2.5}, which is better than the best known one in the range n^{3/2} ≪ S ≪ n^{7/4}. We further extend this improvement to the kSUM-Indexing problem - a generalization of 3SUM-Indexing - and to the related kXOR-Indexing problem, where addition is replaced with XOR. Additionally, we improve the best known time-space tradeoffs for the Jumbled Indexing problem, which is a well-known data structure problem related to 3SUM-Indexing. Our improvement comes from an alternative way to apply the Fiat-Naor algorithm to 3SUM-Indexing. Specifically, we exploit the structure of the function to be inverted by decomposing it into "sub-functions" with certain properties. This allows us to apply an improvement to the Fiat-Naor algorithm (which is not directly applicable to 3SUM-Indexing), obtained in [Golovnev et al., 2023] in a much larger range of parameters. We believe that our techniques may be useful in additional application-dependent optimizations of the Fiat-Naor algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Itai Dinur and Alexander Golovnev 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.78 urn:nbn:de:0030-drops-264674 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.78 eng https://creativecommons.org/licenses/by/4.0/legalcode