We study time/memory tradeoffs of function inversion: an algorithm, i.e., an inverter, equipped with an $s$-bit advice for a randomly chosen function $f\colon [n] \mapsto [n]$ and using $q$ oracle queries to $f$, tries to invert a randomly chosen output $y$ of $f$ (i.e., to find $x$ such that $f(x)=y$). ... more >>>

In function inversion, we are given a function $f: [N] \mapsto [N]$, and want to prepare some advice of size $S$, such that we can efficiently invert any image in time $T$. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower ... more >>>