pipette
ENEnglish

Tarski Fixed Points in Quasi-FPT Queries

Xi Chen, Ruiquan Gao, Yuhao Li, Aviad Rubinstein, Mihalis Yannakakis

Preprint

En palabras de los autores

We study the query complexity of finding a Tarski fixed point over . Previous work has left a large gap between and . We show that both of the previous upper and lower bounds were far from tight: for every , \[ \Omega\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 , the complexity is settled at . In particular, we obtain the first super-polynomial query lower bound for this problem.

Resultado principalLimitación que admiten los autores

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.