The Mysterious Query Complexity of Tarski Fixed Points
- Yuhao Li, Columbia University
- Time: 2026-06-30 14:00
- Host: Prof. Xiaotie Deng
- Venue: Room 102, Courtyard No.5, Jingyuan
Abstract
Tarski's fixed point theorem has extensive applications across many fields, including verification, semantics, game theory, and economics. Recently, the complexity of finding a Tarski fixed point has attracted significant attention.
In this talk, I will introduce the problem of computing a Tarski fixed point over a grid $[N]^d$, highlight recent progress toward a better understanding of it, and discuss the surprising journey and the mysteries surrounding its complexity.
Based on joint work with Xi Chen and Mihalis Yannakakis.
Biography
Yuhao Li is a fifth-year PhD student in the theory group at Columbia University, advised by Xi Chen and Rocco Servedio. Prior to that, he got a B.Sc. degree in computer science from Peking University, advised by Xiaotie Deng. He is broadly interested in theoretical computer science, with a particular focus on complexity theory.