  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. 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(\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 \lceil k/3 \rceil} n)$ query algorithm for the
$k$-dimensional problem.
