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

2024-01-16  14:00 - 15:00   

Speaker

Yuhao Li, Columbia University

Room

Room 308