A Faster Algorithm for Finding Tarski Fixed Points
John Fearnley, Dömötör Pálvölgyi, Rahul Savani · ACM Transactions on Algorithms · 2022
Dang et al. have given an algorithm that can find a Tarski fixed point in a k -dimensional lattice of width n using O (log k n ) queries [ 2 ]. Multiple authors have conjectured that this algorithm is optimal [ 2 , 7 ], and indeed this has been proven for two-dimensional instances [ 7 ]. We show that these conjectures are false in dimension three or higher by giving an O (log 2 n ) query algorithm for the three-dimensional Tarski problem. We also give a new decomposition theorem for k -dimensional Tarski problems which, in combination with our new algorithm for three dimensions, gives an O (log 2 ⌈k/3⌉ n ) query algorithm for the k -dimensional problem.