NobleBlocks

From the research index

The paper comes from the research index. It wasn’t submitted here.

Preprint

Function Inversion Reporting

Itai Dinur, Alexander Golovnev, Chao Yan and 1 other

9 Nov 2026Open access

Abstract

In the Function Inversion problem, the goal is to invert a function $f:[N] \to [N]$ in two phases. In the preprocessing phase, the offline algorithm computes an advice string of length $S$ bits. In the online phase, the online algorithm receives the advice and a challenge $y \in [N]$, and the goal is to find a preimage $x \in [N]$ such that $f(x) = y$ in time $T$. The problem was initially studied in cryptography, but in recent years it has found various applications to data structure problems. Yet, several of the applications require a variant of Function Inversion, known as Function Inversion Reporting, where the goal is to output all preimages of the challenge $y$. In this paper, we study the Function Inversion Reporting problem in a systematic way by unifying and improving existing algorithms. As a result, we obtain improved data structures for several problems including 3SUM-Indexing Reporting, Range Reporting, Approximate Nearest Neighbor, Jumbled Indexing Reporting, and Gapped String Indexing Reporting.

Discussion

Citations

17References

Details

Authors
Itai Dinur, Alexander Golovnev, Chao Yan, Yi-Ding Zhu
Published
9 Nov 2026

More

Suggest a correction or report