Time-Space Tradeoffs for Function Inversion (Siyao Guo)

Abstract

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.

Time

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

Speaker

Siyao Guo, NYU Shanghai

Room

Guangdong Hotel Shanghai