Time Space Tradeoffs for Function Inversion
- 講者郭斯瑤 博士 (上海紐約大學)
邀請人:鐘楷閔 - 時間2023-07-13 (Thu.) 13:30 – 15:30
- 地點資訊所新館101演講廳
摘要
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.