pith. sign in

arxiv: 1907.11206 · v1 · pith:BGCO5D74new · submitted 2019-07-25 · 💻 cs.DS

The Strong 3SUM-INDEXING Conjecture is False

Tsvi Kopelowitz , Ely Porat This is my paper

Pith reviewed 2026-05-24 15:54 UTC · model grok-4.3

classification 💻 cs.DS
keywords 3SUM-Indexingfunction inversionspace-time tradeoffsdata structuresFiat-Naor algorithmpreprocessingquery time
0
0 comments X

The pith

The strong 3SUM-Indexing conjecture is false, as a reduction to function inversion yields an algorithm that beats the conjectured space and query-time limits.

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

The 3SUM-Indexing problem requires preprocessing two lists of n elements so that, given a target value, one can quickly decide whether any pair from the two lists sums to that value. Goldstein et al. conjectured that no solution exists using n to the 2 minus a positive constant amount of space together with n to the 1 minus a positive constant amount of query time. The paper refutes this by constructing a reduction from 3SUM-Indexing to the task of inverting a function, then invoking the Fiat-Naor algorithm for function inversion. Because the reduction maintains the relevant space and query parameters, the known inversion procedure produces concrete bounds that violate the conjectured limits.

Core claim

We show that the conjecture is false by reducing the 3SUM-Indexing problem to the problem of inverting functions, and then applying an algorithm of Fiat and Naor for inverting functions.

What carries the argument

A parameter-preserving reduction from 3SUM-Indexing instances to function-inversion instances.

If this is right

  • 3SUM-Indexing admits a solution with n^{2-Ω(1)} space and n^{1-Ω(1)} query time.
  • The conjecture stated by Goldstein et al. does not hold.
  • Any lower-bound proof that assumed the strong conjecture is now invalid for this parameter regime.

Where Pith is reading between the lines

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

  • Other fine-grained hardness assumptions that rest on the strong 3SUM-Indexing conjecture may require re-examination.
  • The same reduction technique could be tested on related indexing problems such as 3SUM-Reporting or convolution variants.
  • A direct data-structure construction that avoids the intermediate function-inversion step might be possible and could improve constants.

Load-bearing premise

The reduction from 3SUM-Indexing to function inversion keeps the space and query-time parameters intact so that the Fiat-Naor bounds fall inside the region forbidden by the conjecture.

What would settle it

A concrete 3SUM-Indexing instance for which every solution that uses the reduced function-inversion instance requires either more than n to the 2 minus omega of 1 space or more than n to the 1 minus omega of 1 query time under the Fiat-Naor procedure.

read the original abstract

In the 3SUM-Indexing problem the goal is to preprocess two lists of elements from $U$, $A=(a_1,a_2,\ldots,a_n)$ and $B=(b_1,b_2,...,b_n)$, such that given an element $c\in U$ one can quickly determine whether there exists a pair $(a,b)\in A \times B$ where $a+b=c$. Goldstein et al.~[WADS'2017] conjectured that there is no algorithm for 3SUM-Indexing which uses $n^{2-\Omega(1)}$ space and $n^{1-\Omega(1)}$ query time. We show that the conjecture is false by reducing the 3SUM-Indexing problem to the problem of inverting functions, and then applying an algorithm of Fiat and Naor [SICOMP'1999] for inverting functions.

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 / 1 minor

Summary. The paper claims to refute the Strong 3SUM-Indexing Conjecture of Goldstein et al. (WADS 2017) by reducing 3SUM-Indexing (preprocess A,B of size n to answer a+b=c queries) to the function-inversion problem and invoking the Fiat-Naor (SICOMP 1999) inversion algorithm, which is asserted to yield an algorithm using n^{2-Ω(1)} space and n^{1-Ω(1)} query time.

Significance. If the parameter-preserving reduction and the applicability of Fiat-Naor to the constructed function are valid, the result would disprove a well-known conjecture in fine-grained data-structure complexity and would imply improved trade-offs for related sumset problems.

major comments (2)
  1. [reduction and Fiat-Naor application] The reduction constructs a function f on a domain of size N=n² by f(i,j)=a_i+b_j. Fiat-Naor’s S T² ≈ N tradeoff is proved via probabilistic covering arguments that hold with high probability only for random functions. The manuscript must either supply a worst-case version of Fiat-Naor that works for every function or prove that the arithmetic-progression structure of this particular f inherits the same covering probabilities (abstract, paragraph 2 and the reduction section).
  2. [parameter mapping] It is not shown that the space and query-time parameters of the resulting inversion instance map back to 3SUM-Indexing parameters in a way that strictly violates the conjectured n^{2-Ω(1)} / n^{1-Ω(1)} bound; an explicit parameter calculation is required (abstract, paragraph 2).
minor comments (1)
  1. [abstract] The abstract should state the precise space and query exponents obtained from Fiat-Naor rather than only the Ω notation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the constructive major comments. We address each point below. Both issues can be resolved by revisions that add missing details without altering the core claims.

read point-by-point responses

  1. Referee: [reduction and Fiat-Naor application] The reduction constructs a function f on a domain of size N=n² by f(i,j)=a_i+b_j. Fiat-Naor’s S T² ≈ N tradeoff is proved via probabilistic covering arguments that hold with high probability only for random functions. The manuscript must either supply a worst-case version of Fiat-Naor that works for every function or prove that the arithmetic-progression structure of this particular f inherits the same covering probabilities (abstract, paragraph 2 and the reduction section).

    Authors: We agree that the original presentation did not explicitly verify applicability of the Fiat-Naor covering analysis to the structured function f(i,j)=a_i+b_j. In the revision we will add a short subsection showing that the relevant covering probabilities remain high for this f. The argument proceeds by observing that, when A and B are drawn from a universe of size at least n^3, each value f(i,j) is uniformly distributed over a large range and the pairwise collisions needed for the covering lemma occur with the same probability as in the fully random case; the arithmetic-progression structure does not create systematic dependencies that invalidate the union-bound calculations. This establishes that the Fiat-Naor data structure succeeds with high probability on the constructed instance. revision: yes

  2. Referee: [parameter mapping] It is not shown that the space and query-time parameters of the resulting inversion instance map back to 3SUM-Indexing parameters in a way that strictly violates the conjectured n^{2-Ω(1)} / n^{1-Ω(1)} bound; an explicit parameter calculation is required (abstract, paragraph 2).

    Authors: We accept that an explicit calculation is needed for clarity. The revised manuscript will contain the following mapping immediately after the reduction statement: the inversion instance has domain size N=n²; Fiat-Naor supplies a data structure with space S and query time T satisfying S·T² = N^{1-o(1)}. Substituting N=n² yields S = n^{2-o(1)} and T = n^{1-o(1)}, which directly falsifies the strong 3SUM-Indexing conjecture. The same calculation will be inserted into the abstract. revision: yes

Circularity Check

0 steps flagged

No circularity: external reduction to independent 1999 algorithm

full rationale

The paper's central claim is established by an explicit reduction from 3SUM-Indexing to function inversion (preserving space/query parameters) followed by direct invocation of the Fiat-Naor algorithm from SICOMP 1999. This citation is to unrelated prior work by different authors; the derivation contains no self-citations, no fitted parameters renamed as predictions, no self-definitional equations, and no ansatz or uniqueness result imported from the authors' own prior papers. The argument is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the validity of the reduction and the direct applicability of the Fiat-Naor algorithm; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption The Fiat-Naor algorithm applies to the function-inversion instance obtained from the 3SUM-Indexing reduction and yields bounds violating the conjecture.
    This is the load-bearing step that converts the reduction into a counter-example.

pith-pipeline@v0.9.0 · 5680 in / 1120 out tokens · 34443 ms · 2026-05-24T15:54:54.155824+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Improved Time-Space Tradeoffs for 3SUM-Indexing

    cs.DS 2025-12 unverdicted novelty 7.0

    Achieves T S = n^{2.5} time-space tradeoff for 3SUM-Indexing via structured decomposition of the function inverted by Fiat-Naor.

  2. A General Technique for Searching in Implicit Sets via Function Inversion

    cs.DS 2023-11 unverdicted novelty 6.0

    A Fiat-Naor-based inversion technique yields data structures for range searching, counting, and related queries on implicit sets f([N]) with ~O(N^{1-α/3}) space and ~O(N^α) query time for any α ∈ (0,1).

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · cited by 2 Pith papers

  1. [1]

    Popular conjectures imply strong lower bounds for dynamic problems

    Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 434–443, 2014

    work page 2014

  2. [2]

    Consequences of faster alignment of sequences

    Amir Abboud, Virginia Vassilevska Williams, and Oren We imann. Consequences of faster alignment of sequences. In Proceedings of the 41st International Colloquium on Automata , Languages, and Programming (ICALP) , pages 39–51, 2014

    work page 2014

  3. [3]

    Matching triangles and basing hardness on an extremely popular conjecture

    Amir Abboud, Virginia Vassilevska Williams, and Huache ng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC) , pages 41–50, 2015

    work page 2015

  4. [4]

    Chan, Moshe Lewenstein, and Noa Lewenstein

    Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of jumbled indexing. In Proceedings of the 41st International Colloquium on Automata , Languages, and Programming (ICALP) , pages 114–125, 2014

    work page 2014

  5. [5]

    Riva Shalom

    Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie , Ely Porat, and B. Riva Shalom. Mind the gap: Essentially optimal algorithms for online dic tionary matching with one 3See the discussion in Section 3 of [6]. 3 gap. In Proceedings of the 27th International Symposium on Algorith ms and Computation (ISAAC), pages 12:1–12:12, 2016

    work page 2016

  6. [6]

    Rigorous time/space trade-offs fo r inverting functions

    Amos Fiat and Moni Naor. Rigorous time/space trade-offs fo r inverting functions. SIAM J. Comput. , 29(3):790–803, 1999

    work page 1999

  7. [7]

    Overmars

    Anka Gajentaan and Mark H. Overmars. On a class of O(n2) problems in computational geometry. Comput. Geom. , 5:165–185, 1995

    work page 1995

  8. [8]

    How hard is it to find (honest) witnesses? In Proceedings of the 24th Annual European Symposium on Algori thms (ESA), pages 45:1–45:16, 2016

    Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, an d Ely Porat. How hard is it to find (honest) witnesses? In Proceedings of the 24th Annual European Symposium on Algori thms (ESA), pages 45:1–45:16, 2016

    work page 2016

  9. [9]

    Conditional lower bounds for space/time tradeoffs

    Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, an d Ely Porat. Conditional lower bounds for space/time tradeoffs. In Proceedings of the 15th International Symposium on Algorithms and Data Structures (WADS) , pages 421–436, 2017

    work page 2017

  10. [10]

    3sum with preprocessing: Algorithms, lower bounds and cryp tographic applications

    Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Pa rk, and Vinod Vaikuntanathan. 3sum with preprocessing: Algorithms, lower bounds and cryp tographic applications. CoRR, abs/1907.08355, 2019

    work page arXiv 1907

  11. [11]

    Kopelowitz, S

    T. Kopelowitz, S. Pettie, and E. Porat. Higher lower bou nds from the 3SUM conjecture. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium o n Discrete Algo- rithms, SODA , pages 1272–1287, 2016

    work page 2016

  12. [12]

    Dynamic se t intersection

    Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Dynamic se t intersection. In Proceedings 14th International Symposium on Algorithms and Data Structu res (WADS) , pages 470– 481, 2015

    work page 2015

  13. [13]

    Towards polynomial lower bounds for dynamic problems

    Mihai Pˇ atra¸ scu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC) , pages 603–610, 2010

    work page 2010

  14. [14]

    Find ing, minimizing, and counting weighted subgraphs

    Virginia Vassilevska Williams and Ryan Williams. Find ing, minimizing, and counting weighted subgraphs. SIAM J. Comput. , 42(3):831–854, 2013. 4

    work page 2013