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 \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.
Fields of Study & Subjects
Computational Geometry and Mesh Generation
Complexity and Algorithms in Graphs
Fixed Point Theorems Analysis
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 56–64
- Publication date
- 1 January 2026
- Language
- EN