Computing Tarski Fixed Points

Speaker(s)

Paweł Parys

Affiliation

University of Warsaw

Language of the talk

English

Date

June 24, 2026, 2:15 p.m.

Room

room 5440

Title in Polish

Computing Tarski Fixed Points

Seminar

Seminar Automata Theory

---

This is a not-my-theorem talk. I will present recent results by Xi Chen, Yuhao Li, Mihalis Yannakakis on computing Tarski fixed points in the black-box model. In this problem we consider a monotone function F over the k-dimensional grid [n]^k, and we want to compute a fixed point of F, where the only way of accessing F is by querying its value at specific points. In this context, n can be exponentially large, so "polynomial" means polynomial in k and in log(n).

This problem encompasses solving parity games, mean-payoff games, and simple stochastic games.

Theorem 1: A black-box reduction from the Tarski problem to the same problem with additional promise that the input function has a unique fixed point.

Theorem 2: An algorithm with O(log^{^2} n) queries for k=4. More generally, with O(log^{1+\ceil{(k-1)/3}} n) queries.
Previously, O(log^{1+\ceil{(k-1)/2}} n) queries were possible, which gives O(log^{^2} n) only for k=3.

Both theorems are based on a new notion of "safe partial-information functions", which intuitively captures the maximal knowledge that can be deduced from queries performed so far.
 

---