A Levelset Algorithm for 3D-Tarski
Sebastian Haslebacher, Jonas Lill · Society for Industrial and Applied Mathematics eBooks · 2026
We present a simple new algorithm for finding a Tarski fixed point of a monotone function \(F : [N]^3 \rightarrow [N]^3\). Our algorithm runs in \(\mathcal{O}(\log^{2} N)\) time and makes \(\mathcal{O}(\log^{2} N)\) queries to \(F\), matching the \(\Omega(\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.