# A faster algorithm for finding Tarski fixed points

arXiv: https://arxiv.org/abs/2010.02618 · HTML: https://mlsanity.com/paper/2010.02618/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Oct 2020.

## Built on by (most cited first, 1 of 1)

- [Formally Verified Patent Analysis via Dependent Type Theory: Machine-Checkable Certificates from a Hybrid AI + Lean 4 Pipeline](https://mlsanity.com/paper/2604.18882/) (2026)

## Abstract (arXiv)

Dang et al. have given an algorithm that can find a Tarski fixed point in a k-dimensional lattice of width n using O(logk n) queries. Multiple authors have conjectured that this algorithm is optimal [Dang et al., Etessami et al.], and indeed this has been proven for two-dimensional instances [Etessami et al.]. We show that these conjectures are false in dimension three or higher by giving an O(log2 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(log2 lceil k/3 rceil n) query algorithm for the k-dimensional problem.