A Levelset Algorithm for 3D-Tarski

Abstract

We present a simple new algorithm for finding a Tarski fixed point of a monotone function $F:[N{]}^3\to [N{]}^3$. Our algorithm runs in $O({\log }^{2}N)$ time and makes $O({\log }^{2}N)$ queries to $F$, matching the $\hat{I}\text{c◯}({\log }^{2}N)$ query lower bound due to Etessami et al. as well as the existing state-of-the-art algorithm due to Fearnley et al.