cs.GTcs.CCcs.LGmath.OC

A Quasipolynomial Algorithm for $\ell_\infty$ Contractions

📅 👥 2 authors arXiv:2610.30122v1

Authors

Abstract

We give an algorithm for computing an $\eps$-approximate fixed point of any $d$-dimensional nonexpansion with respect to the $\ell_\infty$ norm in time $\log(1/\eps)^{O(\log^2 d)}$. At its core, our method uses a boosting argument to geometrically shrink a search region. Among other consequences, our algorithm implies that simple stochastic games can be solved in quasipolynomial time.

Paper Information

arXiv ID:
2610.30122v1
Published:

Related Categories

cs.GTcs.CCcs.LGmath.OC