Dynamic and Optimal Function Inversion in the Small-Time Regime

Abstract

The classic function-inversion problem considers the task of constructing a data structure which, given access to a constant-time oracle for a function $f:[N]\to [N]$, supports efficient inverse-queries on $f$. This problem has been studied extensively in the small-space/large-time regime, where one wishes to use space $S$, say, $N^{1-\Omega (1)}$ bits, and where the query time is intended to be a small polynomial of $N$. Much less attention has been given to the \emph{small-time/large-space} regime, where $S=(N\log N)/t$ for some relatively small $t$, and where the goal is to achieve a good space bound as a function of $t$. In this paper, we give an optimal solution in the small-time regime, achieving space $S=O(N\log N/t)$ and time $O(t)$ for any $t\le O(\log N/\log \log N)$. This matches a lower bound by Yao (and is the first parameter regime where the lower bound has been matched for general functions). Additionally, we extend our solution to support point-updates to $f$, also in $O(t)$ time. Our techniques for supporting point updates also extend to the classic function-inversion solution of Fiat and Naor. As a sample application of our results, we show how to construct dynamic unordered graphs that use space $(1+\epsilon )$-close to information-theoretically optimal while offering adjacency queries, neighborhood queries, and edge insertions/deletions in amortized time $O({\epsilon }^{-1})$.