# Theory Seminar: Function-Inversion Problem: Barriers and Opportunities

- Speaker:
- Dima Kogan (Stanford University)
- Date:
- Wednesday, 2.1.2019, 12:30
- Place:
- Room 201 Taub Bld.

n the function-inversion problem, an algorithm gets black-box access to a
function $f:[N] \to [N]$ and takes as input a point $y \in [N]$, along with
$S$ bits of auxiliary information about $f$. After running for time $T$, the
algorithm must output an $x \in [N]$ such that $f(x) = y$, if one exists. This
problem, first studied by Hellman (1980), has manifold applications to
cryptanalysis.

Hellman’s algorithm for this problem achieves the time-space tradeoff $S = T =
\tilde{O}(N^{2/3})$ when $f$ is a random function, while the best known lower
bound, due to Yao (1990) shows that $ST = \tilde{\Omega}(N)$, which admits the
possibility of an $S = T = \tilde{O}(N^{1/2})$ algorithm. There remains a
long-standing and vexing gap between these upper and lower bounds.

In this talk, I will present some new connections between function inversion and
other areas of theoretical computer science. These connections suggest that
making progress on either the lower-bound or upper-bound side of this problem
might be challenging. Moreover, we will see how these connections—in concert
with Hellman-style algorithms—improve the best upper bounds for well-studied

problems in communication complexity and data structures.

Joint work with Henry Corrigan-Gibbs.