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

Abstract

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, our algorithm yields an $O({\log }^{\lceil (k-1)/3\rceil +1}n)$-query algorithm for any constant $k$, improving the previous best upper bound $O({\log }^{\lceil (k-1)/2\rceil +1}n)$ of [CL22]. Our algorithm uses a new framework based on \emph{safe partial-information} functions. The latter were introduced in [CLY23] to give a reduction from the Tarski problem to its promised version with a unique fixed point. This is the first time they are directly used to design new algorithms for Tarski fixed points.