The Mysterious Query Complexity of Tarski Fixed Points
Host
Justin Chen, Lily Chung, John Kuszmaul
CSAIL, EECS
October 29 2025
4:00P
- 5:00P
Location
32-G575
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.
Add to Calendar
2025年10月29日 16:00:00
2025年10月29日 17:00:00
America/New_York
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.
TBD