The Mysterious Query Complexity of Tarski Fixed Points

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 our 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.