Tarski Fixed Points in Quasi-FPT Queries

Xi Chen, Ruiquan Gao, Yuhao Li +2

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 tha…