Yuhao Li, Columbia University

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 our recent progress toward a better understanding of it, and discuss the surprising journey and the mysteries surrounding its complexity.

See: https://theory.cs.rutgers.edu/theory_seminar