Tarski Fixed Points in Quasi-FPT Queries

We study the query complexity of finding a Tarski fixed point over $[n{]}^k$. Previous work has left a large gap between $\mathrm{\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$, $$\mathrm{\Omega }((\log n{)}^{\frac{1}{2}\lceil \log k\rceil })\le \mathrm{Tarski}(n,k)\le O(5^k(\log n{)}^{\lceil \log k\rceil })\mathrm{.}$$ Succinctly, up to the fixed-parameter factor of $5^k$, the complexity is settled at $(\log n{)}^{\mathrm{\Theta }(\log k)}$. In particular, we obtain the first super-polynomial query lower bound for this problem.