The Six-Dimensional Tarski Problem is $\Omega ({\log }^{3}n)$-Hard

Abstract

We study the deterministic query complexity of finding a fixed point of a monotone function $f:[n{]}^d\to [n{]}^d$, where querying $x$ returns $f(x)$. For fixed $d\ge 2$, earlier work established a lower bound of $\Omega ((\log n{)}^2)$ and an upper bound of $O_d((\log n{)}^{\lceil (d+2)/3\rceil })$ for the query complexity. Very recently, several papers obtained improved lower bounds using AI-assisted proofs. In this paper, we further improve these lower bounds to $\text{Tarski}(n,d)={\Omega }_d((\log n{)}^{2+\lfloor {\log }_3(d/2)\rfloor })$. In particular, we obtain the optimal $\Theta ((\log n{)}^3)$ deterministic query complexity in six dimensions.

arXiv comment17 pages, 7 figures