Metraipolis › archive › dc_e1d7ff3ef69e

Preprocessed 3SUM: From Reals to Integers — arXiv:2610.21961

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.21961
License (as archived)
CC0-1.0
Archived
2026-10-16T10:40:22.150Z
SHA-256 of the archived text
f718fe38a097ce9f9145fef508ff74caf53a2bdd0918f16aae1e0cee713cf9c5
Stable URL of this page
https://metraipolis.com/documento/dc_e1d7ff3ef69e

How to cite

Preprocessed 3SUM: From Reals to Integers — arXiv:2610.21961 — arXiv (en), https://arxiv.org/abs/2610.21961 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e1d7ff3ef69e (Metraipolis archive dc_e1d7ff3ef69e, sha256 f718fe38a097ce9f9145fef508ff74caf53a2bdd0918f16aae1e0cee713cf9c5)
BibTeX
@misc{dce1d7ff3ef69e,
  title = {Preprocessed 3SUM: From Reals to Integers — arXiv:2610.21961},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.21961},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e1d7ff3ef69e; sha256 f718fe38a097ce9f9145fef508ff74caf53a2bdd0918f16aae1e0cee713cf9c5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.21961. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The Preprocessed 3SUM problem asks to preprocess a set $A$ of $n$ numbers so that we can quickly decide whether a query subset $A' \subseteq A$ contains a solution $a+b=c$. The best known query bounds differ substantially between integer and real inputs. For integers, a series of advances with near-quadratic preprocessing reduced the query time from $\tilde O(n^{13/7})$ [Chan, Lewenstein; STOC '15] to $\tilde O(n^{11/6})$ [Chan, Vassilevska W., Xu; STOC '23], and finally to $\tilde O(n^{3/2})$ [Kasliwal, Polak, Sharma; SOSA '25]. For reals, only the first of these bounds has been achieved, by adapting the corresponding integer algorithm [Fischer; SODA '25]. Is this gap inherent to the more limited tools available for real inputs? We give a randomized real-to-integer reduction with $\tilde O(n^2)$ preprocessing overhead and no asymptotic increase in query time. This yields $\tilde O(n^2)$ preprocessing and $\tilde O(n^{3/2})$ query time for real inputs, closing the gap. We show how to extend our result to the setting where one set is unknown at preprocessing time. Our reduction is conceptually simple, and relies on an interesting technical toolkit around old and new tools from sparse linear algebra. More broadly, it suggests a route to real-to-integer reductions for other additive problems.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.21961 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T08:53:17.675Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).