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

Xi Chen, Yuhao Li, Mihalis Yannakakis

We give an $O({\log }^{2}n)$-query algorithm for finding a Tarski fixed point over the $4$-dimensional lattice $[n{]}^4$, matching the $\Omega ({\log }^{2}n)$ lower bound of [EPRY20]. Additionally…