Time-Space Tradeoffs for Function Inversion (Siyao Guo)
Abstract
In function inversion, we are given a function
f:[N]->[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 bounds. In
this talk, I will describe recent progress in obtaining tight time-space bounds
for function inversion and its related problems.
Time
2021-06-19 11:00-11:30
Speaker
Siyao Guo, NYU Shanghai
Room
Guangdong Hotel Shanghai
