The Mysterious Query Complexity of Tarski Fixed Points

Speaker: LI Yuhao
Columbia University

Title: The Mysterious Query Complexity of Tarski Fixed Points

Date: Thursday, 23 July 2026

Time: 10:30am - 12:00noon

Venue: Room 5402 (via Lift 17/18), HKUST

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.