PreprintarXiv licencearXiv
A Quasipolynomial Algorithm for ℓ∞ Contractions
Abstract
We give an algorithm for computing an eps-approximate fixed point of any d-dimensional nonexpansion with respect to the ℓ∞ norm in time log(1/eps)O(log2 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.
Related
- Cayley graph diameters for fixed cycle types are eventually quasipolynomial
- List 3-Coloring in tame classes of graphs in quasipolynomial time
- Quasipolynomial density bounds for K-point configurations in ℤd
- A quasipolynomial inverse theorem for the Uk(𝔽pn) norm in the high characteristic
- Extended Abstract of Counting Divisorial Contractions with Centre a cAn-Singularity
BibTeX
@misc{soleymani2026quasipolynomial,
title = {{A Quasipolynomial Algorithm for $\ell_\infty$ Contractions}},
author = {Ashkan Soleymani and Gabriele Farina},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30122},
eprint = {2610.30122},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30122},
}
RIS
TY - UNPB
TI - A Quasipolynomial Algorithm for ℓ_∞ Contractions
AU - Ashkan Soleymani
AU - Gabriele Farina
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.30122
UR - https://arxiv.org/abs/2610.30122
AB - We give an algorithm for computing an eps-approximate fixed point of any d-dimensional nonexpansion with respect to the ℓ_∞ 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.
ER -