M. Yannakakis

collaborators

2 papers

cs.CC2026

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points

Xi Chen, Yuhao Li, Mihalis Yannakakis

We give an $O (lo g^{2} n)$ -query algorithm for finding a Tarski fixed point over the $4$ -dimensional lattice $[n]^{4}$ , matching the $I^c ◯ (lo g^{2} n)$ lower bound of [EPRY20]. Additionall…

cs.CC2025

Computing a Fixed Point of Contraction Maps in Polynomial Queries

Xi Chen, Yuhao Li, Mihalis Yannakakis

We give an algorithm for finding an $I^µ$ -fixed point of a contraction map $f : [0, 1]^{k} \mapsto [0, 1]^{k}$ under the $ℓ_{\infty}$ -norm with query complexity $O (k lo g (1/ I^µ))$ .