Preprint
Oct 2026
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 $\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 \l...
Xi Chen, Rui-Quan Gao, Yu-Hao Li et al.
· 0 citations