Time-Space Tradeoffs for Function Inversion (Siyao Guo)


In function inversion, we are given a functionf:[N]->[N], and want to prepare some advice of size S, such that we canefficiently invert any image in time T. This is a well studied problem withprofound connections to cryptography, data structures, communicationcomplexity, and circuit lower bounds.  Inthis talk, I will describe recent progress in obtaining tight time-space boundsfor function inversion and its related problems.


2021-06-19  11:00-11:30   


Siyao Guo, NYU Shanghai


Guangdong Hotel Shanghai