Abstract
Tarski's fixed point theorem has extensive applications in many fields, including for example verification, semantics, game theory and economics. The complexity of finding a Tarski fixed point has recently gained a lot of attention.
In this talk, I will introduce the problem of computing a Tarski fixed point over a -dimensional grid , people's surprising journey over the past few years, and our recent progress toward a better understanding of it.
Based on two recent works:
Improved Upper Bounds for Finding Tarski Fixed Points. Xi Chen, Yuhao Li. EC 2022
Reducing Tarski to Unique Tarski (in the Black-box Model). Xi Chen, Yuhao Li, Mihalis Yannakakis. CCC 2023
Time
Tuesday, Jan.16, 14:00--15:00
Speaker
Yuhao Li is a third-year PhD student in the theory group at Columbia University, where he is fortunate to be advised by Prof. Xi Chen and Prof. Rocco Servedio. Prior to that, he got a B.Sc. degree in computer science from Peking University, where he was fortunate to be advised by Prof. Xiaotie Deng.
His research interests broadly lie in theoretical computer science, especially complexity theory and algorithmic game theory.
Room
信管学院308室
