pith. sign in

arxiv: 2311.12471 · v2 · submitted 2023-11-21 · 💻 cs.DS

A General Technique for Searching in Implicit Sets via Function Inversion

Boris Aronov , Jean Cardinal , Justin Dallant , John Iacono This is my paper

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

classification 💻 cs.DS
keywords implicit setsrange searchingdata structuresspace-time tradeoffsfunction inversionpreimage queriesgeometric queriesstring indexing
0
0 comments X

The pith

If a function from [N] to a d-dimensional grid evaluates in constant time, its image admits a data structure for box search with space roughly N to the power 1 minus alpha over 3 and query time N to the alpha.

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 build data structures that answer queries about the image of a function without storing the image points explicitly. It achieves a flexible space-time tradeoff for finding whether any output point falls inside a given axis-aligned box. The same approach extends to counting, reporting, ordering, and ranking operations on the image, plus some geometric statistics computed from pairs or tuples of those points. Readers care because the technique turns many problems whose sets are defined implicitly by a fast function into instances of a single searchable structure. It recovers known results for string search and 3SUM indexing as special cases.

Core claim

If f maps [N] into [2^w]^d with w equal to polylog(N) and evaluates in constant time, then for any alpha between 0 and 1 a data structure of size roughly N to the power 1 minus alpha over 3 answers box queries by returning some x whose image lies inside the box in time roughly N to the alpha. The same inversion method yields structures for range counting, reporting, predecessor, selection, and ranking queries on the image set, for preimage size and selection, and for selection and ranking on geometric quantities derived from tuples of image points.

What carries the argument

Adaptation of function inversion to locate a preimage whose output coordinate vector lies inside a query box.

Load-bearing premise

The function maps each input in [N] to a d-dimensional grid point whose coordinates fit in polylog(N) bits and can be evaluated in constant time.

What would settle it

A single function f from [N] to the grid that evaluates in constant time yet admits no data structure achieving the stated space and query-time bounds for box search.

read the original abstract

In recent years, the Fiat-Naor function inversion scheme has been used to disprove conjectures in fine-grained complexity theory and design state of the art data structures for a number of combinatorial problems. We pursue this line of research by considering its application to data structures for searching in implicit sets, defined as the image of a function. We show that, if $f$ is of the form $[N]\to [2^{w}]^d$ for some $w=polylog(N)$ and is computable in constant time, then, for any $0<\alpha <1$, we can obtain a data structure using $\~O(N^{1-\alpha/3})$ space such that, for a given $d$-dimensional axis-aligned box $B$, we can search for some $x\in [N]$ such that $f(x) \in B$ in time $\~O(N^{\alpha})$. (Here the $\~O(.)$ notation omits polylogarithmic factors.) Using similar techniques, we further obtain - data structures for range counting and reporting, predecessor, selection, ranking queries, and combinations thereof, on the set $f([N])$, - data structures for preimage size and preimage selection queries for a given value of $f$, and - data structures for selection and ranking queries on geometric quantities computed from tuples of points in $d$-space. These results unify and generalize previously known results on 3SUM-indexing and string searching, and are widely applicable as a black box to a variety of problems. In particular, we give a data structure for a generalized version of gapped string indexing, and show how to preprocess a set of points on an integer grid in order to efficiently compute (in sublinear time), for points contained in a given axis-aligned box, their Theil-Sen estimator, the $k$th largest area triangle, or the induced hyperplane that is the $k$th furthest from the origin.

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

0 major / 3 minor

Summary. The paper develops a general technique based on the Fiat-Naor function-inversion scheme for building data structures on implicit sets (images of functions f:[N]→[2^w]^d with w=polylog(N) and constant-time evaluation). The central result states that, for any 0<α<1, there exists a data structure using ~O(N^{1-α/3}) space that answers, in ~O(N^α) time, whether there exists an x∈[N] with f(x) inside a given d-dimensional axis-aligned box B. The same framework yields data structures for range counting/reporting, predecessor/selection/ranking on f([N]), preimage-size and preimage-selection queries, and selection/ranking on geometric quantities derived from point tuples; applications include a generalized gapped-string index and sublinear-time computation of Theil-Sen estimators, k-th largest triangle areas, and k-th furthest hyperplanes on grid points. The results are presented as unifying 3SUM-indexing and string searching.

Significance. If the stated space-time bounds are correctly derived from the Fiat-Naor parameters under the given modeling assumptions on f, the work supplies a reusable black-box primitive that generalizes several known data-structure results and can be plugged into fine-grained complexity arguments. The conditional nature of the main theorem (explicitly tied to the range and evaluation cost of f) makes the contribution modular rather than universal.

minor comments (3)
  1. The abstract and introduction should explicitly state the precise parameter regime (including the dependence of the hidden polylog factors on w and d) under which the ~O(N^{1-α/3}) space bound holds; this is needed to verify that the exponent 1-α/3 follows directly from the Fiat-Naor trade-off without additional assumptions.
  2. Section 3 (or wherever the main reduction is presented) should include a short self-contained recap of the Fiat-Naor inversion parameters used, so that readers can see exactly how the α/3 exponent arises.
  3. The applications to geometric queries (Theil-Sen estimator, k-th largest area triangle) would benefit from a brief table comparing the new bounds with the best previously known bounds for those specific problems.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment, the recognition of the work as a reusable modular primitive, and the recommendation of minor revision. The conditional framing tied to the modeling assumptions on f is intentional and matches our presentation. No specific major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation applies external Fiat-Naor scheme to explicit modeling assumptions

full rationale

The central theorem states space and time bounds explicitly conditional on f mapping [N] to [2^w]^d (w=polylog(N)) with constant-time evaluation; these bounds are obtained by invoking the prior Fiat-Naor inversion result as a black-box building block and combining it with standard range-query techniques. No equations reduce a claimed prediction to a fitted parameter by construction, no self-citation chain is load-bearing for the uniqueness or correctness of the bounds, and the modeling choice on f is stated upfront rather than derived internally. The result therefore remains self-contained against external benchmarks and does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no concrete free parameters, axioms, or invented entities can be extracted from the provided text.

pith-pipeline@v0.9.0 · 5911 in / 1272 out tokens · 41278 ms · 2026-05-24T05:53:55.788118+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

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

  1. [1]

    Time and space efficient collinearity indexing

    Boris Aronov, Esther Ezra, Micha Sharir, and Guy Zigdon. Time and space efficient collinearity indexing. Comput. Geom. , 110:101963, 2023. https://doi.org/10.1016/j.comgeo.2022.101963 doi:10.1016/j.comgeo.2022.101963

    work page doi:10.1016/j.comgeo.2022.101963 2023

  2. [2]

    Subquadratic algorithms for algebraic 3SUM

    Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aur \' e lien Ooms, and Noam Solomon. Subquadratic algorithms for algebraic 3SUM . Discret. Comput. Geom. , 61(4):698--734, 2019. https://doi.org/10.1007/s00454-018-0040-y doi:10.1007/s00454-018-0040-y

    work page doi:10.1007/s00454-018-0040-y 2019

  3. [3]

    Selecting distances in arrangements of hyperplanes spanned by points

    Sergei Bespamyatnikh and Michael Segal. Selecting distances in arrangements of hyperplanes spanned by points. J. Discrete Algorithms , 2(3):333--345, 2004. https://doi.org/10.1016/j.jda.2003.12.001 doi:10.1016/j.jda.2003.12.001

    work page doi:10.1016/j.jda.2003.12.001 2004

  4. [4]

    Pissis, Eva Rotenberg, and Teresa Anna Steiner

    Philip Bille, Inge Li G rtz, Moshe Lewenstein, Solon P. Pissis, Eva Rotenberg, and Teresa Anna Steiner. Gapped string indexing in subquadratic space and sublinear query time. Manuscript, 2022. https://doi.org/10.48550/arXiv.2211.16860 doi:10.48550/arXiv.2211.16860

    work page doi:10.48550/arxiv.2211.16860 2022

  5. [5]

    A strong and easily computable separation bound for arithmetic expressions involving radicals

    Christoph Burnikel, Rudolf Fleischer, Kurt Mehlhorn, and Stefan Schirra. A strong and easily computable separation bound for arithmetic expressions involving radicals. Algorithmica , 27(1):87--99, 2000. https://doi.org/10.1007/s004530010005 doi:10.1007/s004530010005

    work page doi:10.1007/s004530010005 2000

  6. [6]

    Improved algebraic degeneracy testing

    Jean Cardinal and Micha Sharir. Improved algebraic degeneracy testing. In Erin W. Chambers and Joachim Gudmundsson, editors, 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA , volume 258 of LIPIcs , pages 22:1--22:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2023. https://doi.org/10.423...

    work page doi:10.4230/lipics.socg.2023.22 2023

  7. [7]

    Some techniques for geometric searching with implicit set representations

    Bernard Chazelle. Some techniques for geometric searching with implicit set representations. Acta Informatica , 24(5):565--582, 1987. https://doi.org/10.1007/BF00263295 doi:10.1007/BF00263295

    work page doi:10.1007/bf00263295 1987

  8. [8]

    The function-inversion problem: Barriers and opportunities

    Henry Corrigan - Gibbs and Dmitry Kogan. The function-inversion problem: Barriers and opportunities. In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography - 17th International Conference, TCC 2019, Nuremberg, Germany, December 1-5, 2019, Proceedings, Part I , volume 11891 of Lecture Notes in Computer Science , pages 393--421. Springer, 2019. ...

    work page doi:10.1007/978-3-030-36030-6_16 2019

  9. [9]

    Optimal suffix tree construction with large alphabets

    Martin Farach. Optimal suffix tree construction with large alphabets. In 38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997 , pages 137--143. IEEE Computer Society, 1997. https://doi.org/10.1109/SFCS.1997.646102 doi:10.1109/SFCS.1997.646102

    work page doi:10.1109/sfcs.1997.646102 1997

  10. [10]

    Rigorous time/space trade-offs for inverting functions

    Amos Fiat and Moni Naor. Rigorous time/space trade-offs for inverting functions. SIAM J. Comput. , 29(3):790--803, 1999. https://doi.org/10.1137/S0097539795280512 doi:10.1137/S0097539795280512

    work page doi:10.1137/s0097539795280512 1999

  11. [11]

    Overmars

    Anka Gajentaan and Mark H. Overmars. On a class of O (n^2) problems in computational geometry. Comput. Geom. , 45(4):140--152, 2012. https://doi.org/10.1016/j.comgeo.2011.11.006 doi:10.1016/j.comgeo.2011.11.006

    work page doi:10.1016/j.comgeo.2011.11.006 2012

  12. [12]

    o rg - R \

    Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. Conditional lower bounds for space/time tradeoffs. In Faith Ellen, Antonina Kolokolova, and J \" o rg - R \" u diger Sack, editors, Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John's, NL, Canada, July 31 - August 2, 2017, Proceedings , volume 10389 of Lect...

    work page doi:10.1007/978-3-319-62127-2_36 2017

  13. [13]

    Data structures meet cryptography: 3SUM with preprocessing

    Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, and Vinod Vaikuntanathan. Data structures meet cryptography: 3SUM with preprocessing. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June ...

    work page doi:10.1145/3357713.3384342 2020

  14. [14]

    Threesomes, degenerates, and love triangles

    Allan Gr nlund and Seth Pettie. Threesomes, degenerates, and love triangles. J. ACM , 65(4):22:1--22:25, 2018. https://doi.org/10.1145/3185378 doi:10.1145/3185378

    work page doi:10.1145/3185378 2018

  15. [15]

    Dynamic point location in fat hyperrectangles with integer coordinates

    John Iacono and Stefan Langerman. Dynamic point location in fat hyperrectangles with integer coordinates. In Proceedings of the 12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, Canada, August 16-19, 2000 , 2000. URL: http://www.cccg.ca/proceedings/2000/30.ps.gz

    work page 2000

  16. [16]

    Kane, Shachar Lovett, and Shay Moran

    Daniel M. Kane, Shachar Lovett, and Shay Moran. Near-optimal linear decision trees for k- SUM and related problems. J. ACM , 66(3):16:1--16:18, 2019. https://doi.org/10.1145/3285953 doi:10.1145/3285953

    work page doi:10.1145/3285953 2019

  17. [17]

    The Strong 3SUM-INDEXING Conjecture is False

    Tsvi Kopelowitz and Ely Porat. The strong 3SUM - INDEXING conjecture is false. Manuscriptds, 2019. URL: http://arxiv.org/abs/1907.11206

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  18. [18]

    Udi Manber and Eugene W. Myers. Suffix arrays: A new method for on-line string searches. SIAM J. Comput. , 22(5):935--948, 1993. https://doi.org/10.1137/0222058 doi:10.1137/0222058

    work page doi:10.1137/0222058 1993

  19. [19]

    Dan E. Willard. Log-logarithmic worst-case range queries are possible in space (n) . Inf. Process. Lett. , 17(2):81--84, 1983. https://doi.org/10.1016/0020-0190(83)90075-3 doi:10.1016/0020-0190(83)90075-3

    work page doi:10.1016/0020-0190(83)90075-3 1983