Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-231 | 6th October 2026 05:20

Tarski Fixed Points in Quasi-FPT Queries

RSS-Feed




TR26-231
Authors: Xi Chen, Ruiquan Gao, Yuhao Li, Aviad Rubinstein, Mihalis Yannakakis
Publication: 6th October 2026 05:39
Downloads: 28
Keywords: 


Abstract:

We study the query complexity of finding a Tarski fixed point over $[n]^k$. Previous work has left a large gap between $\smash{{\Omega}(\log^2 n)}$ and $\smash{\log^{O(k)}n}$. We show that both of the previous upper and lower bounds were far from tight: for every $k\geq 3$,
$$
\Omega\left((\log n)^{\frac{1}{2}\lceil \log k\rceil}\right)\le
\textrm{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.



ISSN 1433-8092 | Imprint