Metraipolis › archive › dc_5fad2eae43e8

From Function Inversion to Preimage Reporting — arXiv:2611.09656

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.09656
License (as archived)
CC0-1.0
Archived
2026-11-09T22:47:15.465Z
SHA-256 of the archived text
9f13e6125e3fa279b36fdfc2fa697baae4313215ec2dfc3806c36027016b26a4
Stable URL of this page
https://metraipolis.com/documento/dc_5fad2eae43e8

How to cite

From Function Inversion to Preimage Reporting — arXiv:2611.09656 — arXiv (en), https://arxiv.org/abs/2611.09656 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5fad2eae43e8 (Metraipolis archive dc_5fad2eae43e8, sha256 9f13e6125e3fa279b36fdfc2fa697baae4313215ec2dfc3806c36027016b26a4)
BibTeX
@misc{dc5fad2eae43e8,
  title = {From Function Inversion to Preimage Reporting — arXiv:2611.09656},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.09656},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5fad2eae43e8; sha256 9f13e6125e3fa279b36fdfc2fa697baae4313215ec2dfc3806c36027016b26a4},
  year = {2026}
}

Archived text

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

Given an arbitrary function $f:[N]\to[M]$, the function inversion problem asks to preprocess $f$ and to be able to, when given some $y\in [M]$, decide whether there exists some $x\in [N]$ such that $f(x)=y$ and if so, to report such an $x$. Recently, Fiat-Naor's solution to this problem has seen significant traction in theoretical computer science, and allowed for several conjectures related to meta-complexity and the 3SUM problem to be broken. In this paper, we consider the natural extension of the function inversion problem that we call preimage reporting. Here, instead of having to report only one $x\in [N]$ such that $f(x)=y$, the whole set $f^{-1}(y)$ must be found. We present a new general method to convert any arbitrary function inversion scheme into an efficient corresponding preimage reporting scheme. In particular, if $\Delta$ is the maximal indegree of $f$, we show that we can perform preimage reporting using space $S$ in time $T$ for any $T$ and $S$ satisfying $TS^2=N^2 \Delta$, matching a variant of a tradeoff obtained by Fiat and Naor for function inversion. This last result implies an improvement over the corresponding function inversion scheme itself, which constitutes the first function inversion scheme whose query time is inversely proportional to $|f^{-1}(y)|$. We derive new simple solutions for the $k$SUM-indexing with reporting and Jumbled indexing with reporting 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/2611.09656 — 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-11-09T22:40:29.881Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).