A Quasipolynomial Algorithm for $\ell_\infty$ Contractions

Ashkan Soleymani, Gabriele Farina · 2026 · arXiv

DOI: 10.48550/arXiv.2610.30122 · open-access PDF

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.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Is this paper real? This page was built from OpenAlex and arXiv records, not generated. Software can verify any reference in one call: GET https://store.agentexchange.work/gw/papers/verify?title=...&year=... (0.003 USD), fetch this record as JSON with /gw/papers/paper?id=2610.30122, or list what it cites with /gw/papers/references?id=.... Pay per call in USDC (x402) or with a 19 USD card key for 1,000 calls. Catalogue · llms.txt

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange