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.
A Quasipolynomial Algorithm for $\ell_\infty$ Contractions
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.
- Preview
- Year
- 2026
- Hosting
- Abstract onlyARXIV-DEFAULT
Cite
Notes
Only stored in your browser.
Attribution
- Abstract & full text
- arxiv.org/abs/2610.30122ARXIV-DEFAULT
- TL;DR
- Semantic Scholar