Institute of Information Science, Academia Sinica

In function inversion, we are given a function from n bits to n bits, and want to prepare some advice of size S, such that we can efficiently invert any image in time T.  Function inversion is a central task in cryptography with profound connections to data structures, communication complexity, and circuit lower bounds.  In This talk, I will describe recent progress in obtaining tight time-space bounds for function inversion and its related problems.