EUVIMEDEUVIMED entdecken
Crossref

A General Technique for Searching in Implicit Sets via Function Inversion

Boris Aronov, Jean Cardinal, Justin Dallant, John Iacono

Algorithmica · 2026-06 · 88 (3)

DOI: 10.1007/s00453-026-01385-5 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithmica, online erschienen am 13.04.2026. Verfasst von Boris Aronov und 3 weiteren Autor:innen. Die Arbeit nennt 37 Literaturangaben. Gefördert von: NSF.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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. Given a function f from the set [N] to a d-dimensional integer grid, we consider data structures that allow efficient orthogonal range searching queries in the image of f, without explicitly storing it. We show that if f is of the form [N]→[2w]d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$[N]\rightarrow [2^{w}]^d$$\end{document} for some w=polylog(N)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w=\textrm{polylog} (N)$$\end{document} and is computable in constant time, then, for any 0

Förderung

  • NSF

Zitieren

APA

Aronov, B., Cardinal, J., Dallant, J., & Iacono, J. (2026). A General Technique for Searching in Implicit Sets via Function Inversion. Algorithmica, 88(3). https://doi.org/10.1007/s00453-026-01385-5

Vancouver

Aronov B, Cardinal J, Dallant J, Iacono J. A General Technique for Searching in Implicit Sets via Function Inversion. Algorithmica. 2026;88(3). doi:10.1007/s00453-026-01385-5

BibTeX
@article{Aronov2026,
  author = {Aronov, Boris and Cardinal, Jean and Dallant, Justin and Iacono, John},
  title = {A General Technique for Searching in Implicit Sets via Function Inversion},
  journal = {Algorithmica},
  year = {2026},
  volume = {88},
  number = {3},
  doi = {10.1007/s00453-026-01385-5}
}
Kostenlos starten →