Given an arbitrary function $f:[N]\to[M]$, the function inversion problem asks to preprocess $f$ so that for any query $y\in[M]$ one can decide whether there exists $x\in[N]$ with $f(x)=y$ and, if so, return one such $x$. Fiat‑Naor’s solution has attracted much attention in theoretical computer science, enabling breakthroughs on several meta‑complexity and 3SUM conjectures. This paper studies a natural extension called preimage reporting: instead of returning a single preimage, the entire set $f^{-1}(y)$ must be reported. We present a general transformation that turns any function inversion scheme into an efficient preimage reporting scheme. Let $\Delta$ denote the maximal indegree of $f$. For any space $S$ and query time $T$ satisfying $TS^{2}=N^{2}\Delta$, preimage reporting can be performed, matching a variant of the Fiat‑Naor space‑time trade‑off for inversion. Remarkably, this yields a query time inversely proportional to $|f^{-1}(y)|$, improving on the original inversion scheme. Using this framework we derive simple solutions for $k$SUM‑indexing with reporting and Jumbled indexing with reporting.
Review: By extending the classic Fiat‑Naor trade‑off to full preimage reporting, the paper achieves a query time that scales inversely with the size of the preimage set, offering a versatile tool for indexing problems that require exhaustive reporting.