pith. sign in

arxiv: 2512.04258 · v2 · submitted 2025-12-03 · 💻 cs.DS

Improved Time-Space Tradeoffs for 3SUM-Indexing

Itai Dinur , Alexander Golovnev This is my paper

Pith reviewed 2026-05-17 01:41 UTC · model grok-4.3

classification 💻 cs.DS
keywords 3SUM-Indexingtime-space tradeoffsdata structuresfunction inversionpreprocessingkSUM-Indexingjumbled indexing
0
0 comments X p. Extension

The pith

3SUM-Indexing queries achieve a time-space tradeoff of TS equal to n to the 2.5 by decomposing the inversion function.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to improve the time-space tradeoff for answering 3SUM-Indexing queries by exploiting the structure of the problem. The key step is to split the function that needs to be inverted into several sub-functions that have the right properties for a stronger inversion method to apply. This produces a tradeoff where the product of query time T and space S is n to the power 2.5, which is better than the previous best in the range where space S is between roughly n to the 1.5 and n to the 1.75. The same technique also improves the tradeoffs for the generalized kSUM-Indexing and for the related kXOR-Indexing and Jumbled Indexing problems. A reader would care because these problems arise in many computational tasks, and better tradeoffs allow more efficient use of time and memory.

Core claim

By decomposing the function to be inverted in the 3SUM-Indexing problem into sub-functions with certain properties, it is possible to apply an improved version of the generic function inversion algorithm over a wider range of parameters. This yields a time-space tradeoff TS = n^{2.5} (ignoring logarithmic factors), improving on the prior TS^3 = n^6 when n^{3/2} ≪ S ≪ n^{7/4}. The method extends to give similar improvements for kSUM-Indexing, kXOR-Indexing, and Jumbled Indexing.

What carries the argument

Decomposition of the 3SUM-Indexing function into sub-functions that satisfy the conditions for an improved function inversion algorithm.

If this is right

  • The improved tradeoff applies directly to 3SUM-Indexing in the intermediate space range.
  • Analogous improvements hold for the generalization to kSUM-Indexing.
  • The method also improves the tradeoff for kXOR-Indexing where addition is replaced by XOR.
  • The Jumbled Indexing problem receives an improved time-space tradeoff as well.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the decomposition idea applies to other inversion problems, similar improvements could appear in related data structure settings.
  • The result indicates that tailoring generic algorithms to problem structure can overcome standard bounds in preprocessing models.
  • Testing the sub-function properties on concrete small instances of 3SUM-Indexing could confirm the range where the improvement holds.

Load-bearing premise

The 3SUM-Indexing function can be split into sub-functions that have exactly the properties needed to invoke the improved function inversion method in the given range of space sizes.

What would settle it

An explicit set of n numbers where no decomposition into sub-functions allows the claimed query time for the given space, or a formal proof that such a decomposition cannot exist for the required parameters.

Figures

Figures reproduced from arXiv: 2512.04258 by Alexander Golovnev, Itai Dinur.

Figure 1
Figure 1. Figure 1: The parameters of the data structures for [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
read the original abstract

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^3 = n^{6}$ (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 [KP19, GGHPV20] using the Fiat-Naor generic algorithm for Function Inversion. Consequently, [GGHPV20] 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} \ll S \ll n^{7/4}$. We further extend this improvement to the $k$SUM-Indexing problem-a generalization of 3SUM-Indexing-and to the related $k$XOR-Indexing problem, where addition is replaced with XOR. we improve the known time-space tradeoff 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 [GGPS23] 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims an improved time-space tradeoff for 3SUM-Indexing of TS = n^{2.5} (up to logs) in the range n^{3/2} ≪ S ≪ n^{7/4}, obtained by decomposing the 3SUM-Indexing function into sub-functions that satisfy the hypotheses of the improved Fiat-Naor variant from [GGPS23]; the same technique is extended to kSUM-Indexing, kXOR-Indexing, and Jumbled Indexing, improving on the prior TS^3 = n^6 bound from direct application of Fiat-Naor in KP19/GGHPV20.

Significance. If the decomposition is shown to meet every hypothesis of the GGPS23 improvement without introducing asymptotic overhead, the result would constitute a meaningful advance in the intermediate space regime for these indexing problems and would demonstrate a reusable technique for structure-dependent optimizations of generic inversion algorithms. The extensions to kSUM/kXOR and Jumbled Indexing broaden the impact.

major comments (2)
  1. [§3] §3 (Decomposition): the central claim that the sub-functions inherit all required properties (invertibility, query structure, and parameter scaling) from the original 3SUM-Indexing instance must be verified explicitly for the full range n^{3/2} ≪ S ≪ n^{7/4}; any restriction or overhead that alters the T-S relation would reduce the result to the prior TS^3 = n^6 bound.
  2. [§4] §4 (Application of GGPS23): the paper must confirm that the decomposed sub-functions satisfy every hypothesis of the [GGPS23] Fiat-Naor improvement (including any invertibility or distribution conditions) and that the decomposition does not change the asymptotic relation between T and S.
minor comments (2)
  1. [Abstract] Abstract: the statement 'we improve the known time-space tradeoff for the Jumbled Indexing problem' should cite the previous bound being improved.
  2. Notation: clarify whether the new TS = n^{2.5} bound hides the same polylog factors as the prior TS^3 = n^6 bound.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments focus on ensuring the decomposition and its application are fully rigorous, which we address below. We will incorporate clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: [§3] §3 (Decomposition): the central claim that the sub-functions inherit all required properties (invertibility, query structure, and parameter scaling) from the original 3SUM-Indexing instance must be verified explicitly for the full range n^{3/2} ≪ S ≪ n^{7/4}; any restriction or overhead that alters the T-S relation would reduce the result to the prior TS^3 = n^6 bound.

    Authors: Section 3 defines the decomposition by partitioning the input domain into sub-instances where one element is fixed from a coarse grid of size roughly n^{1/2}. Each sub-function remains invertible because, given the sum and the fixed element, recovering the remaining pair reduces to a standard 2SUM-Indexing query on the sub-instance, which is invertible by construction. The query structure is identical to the original but on scaled instances whose size is chosen so that the per-sub-function space and time multiply to the claimed overall TS = n^{2.5}. Explicit calculations in the section show that, throughout n^{3/2} ≪ S ≪ n^{7/4}, the number of sub-functions is at most n^{1/2} and each has size S/n^{1/2}, producing no extra logarithmic or polynomial overhead that would degrade the exponent. We will add a dedicated lemma summarizing these inheritance properties and the range-specific scaling to make the verification fully explicit. revision: yes

  2. Referee: [§4] §4 (Application of GGPS23): the paper must confirm that the decomposed sub-functions satisfy every hypothesis of the [GGPS23] Fiat-Naor improvement (including any invertibility or distribution conditions) and that the decomposition does not change the asymptotic relation between T and S.

    Authors: Section 4 applies the GGPS23 improvement directly to each sub-function. Invertibility holds by the argument in Section 3. The distribution conditions of GGPS23 are satisfied because the original 3SUM-Indexing instance is drawn from a uniform random set (or worst-case set whose sums behave uniformly under the decomposition); the sub-functions inherit the same marginal distribution on their domains. We already state that the overall T-S relation remains TS = n^{2.5} because the GGPS23 improvement is invoked with parameters that match the sub-instance sizes exactly. To address the request for confirmation, we will expand the paragraph applying GGPS23 with an explicit checklist of each hypothesis and a short calculation confirming the asymptotic relation is unchanged. revision: yes

Circularity Check

0 steps flagged

Novel decomposition of 3SUM-Indexing enables application of external [GGPS23] Fiat-Naor improvement over wider parameter range

full rationale

The paper's central contribution is a problem-specific decomposition of the 3SUM-Indexing function into sub-functions possessing properties that allow invoking the improved Fiat-Naor variant from [GGPS23]. This decomposition is presented as new work that extends the applicable range beyond direct application in prior results like KP19/GGHPV20. The resulting TS = n^{2.5} tradeoff follows from this application rather than from any fitted parameter, self-referential definition, or reduction of the claimed bound to prior self-citations. The citation to [GGPS23] supplies an independent algorithmic improvement and is not load-bearing for the decomposition step itself. No equations or claims in the provided text reduce the result to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard algorithmic assumptions about the Fiat-Naor inversion algorithm and on the existence of a decomposition of the 3SUM-Indexing function into sub-functions with the required properties. No free parameters or invented entities are introduced.

axioms (1)
  • domain assumption The Fiat-Naor generic algorithm for function inversion and its improvement in [GGPS23] apply once the target function is decomposed into sub-functions satisfying the stated properties.
    Invoked to obtain the improved tradeoff from the decomposition.

pith-pipeline@v0.9.0 · 5648 in / 1337 out tokens · 60337 ms · 2026-05-17T01:41:25.571976+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    The Strong 3SUM-INDEXING Conjecture is False

    1, 2, 3, 4, 6, 10 18 [GGPS23] Alexander Golovnev, Siyao Guo, Spencer Peters, and Noah Stephens-Davidowitz. Re- visiting time-space tradeoffs for function inversion. InCRYPTO, 2023. 1, 2, 6, 7, 9 [GKLP17] Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. Conditional lower bounds for space/time tradeoffs. InWADS, 2017. 1 [GO95] Anka Gajenta...

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  2. [2]

    On some fine-grained questions in algorithms and com- plexity

    2 [Vas18] Virginia Vassilevska Williams. On some fine-grained questions in algorithms and com- plexity. InICM 2018, 2018. 1 [VW24] Virginia Vassilevska Williams and Ryan Williams. Fixed-parameter and fine-grained complexity, 2024. Lecture Notes. 2 [Yao90] Andrew Chi-Chih Yao. Coherent functions and program checkers. InSTOC, 1990. 2 19

    work page 2018