The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
This work addresses a theoretical computer science problem related to query complexity in lattice theory, offering incremental improvements in algorithmic efficiency.
The paper tackles the problem of finding Tarski fixed points in high-dimensional lattices, presenting an algorithm with an O(log^2 n) query complexity for 4-dimensional lattices that matches the known lower bound, and improves the upper bound for constant dimensions k.
We give an $O(\log^2 n)$-query algorithm for finding a Tarski fixed point over the $4$-dimensional lattice $[n]^4$, matching the $Ω(\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.