Tarski Fixed Points in Quasi-FPT Queries

Abstract

We study the query complexity of finding a Tarski fixed point over $[n{]}^k$. Previous work has left a large gap between $\Omega ({\log }^{2}n)$ and ${\log }^{O(k)}n$. We show that both of the previous upper and lower bounds were far from tight: for every $k\ge 3$, \[ Ω\left((\log n)^{\frac{1}{2}\lceil \log k\rceil}\right)\le \operatorname{Tarski}(n,k)\le O\left(5^k(\log n)^{\lceil \log k\rceil}\right). \] Succinctly, up to the fixed-parameter factor of $5^k$, the complexity is settled at $(\log n{)}^{\Theta (\log k)}$. In particular, we obtain the first super-polynomial query lower bound for this problem.