Prof. Itai Dinur

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 TS³ = 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 [22, 17] using the Fiat-Naor generic algorithm for Function Inversion. Consequently, [17] 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 TS = n^2.5, which is better than the best known one in the range n³/² ≪ S ≪ n⁷/⁴. 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 [18] 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.