{"id":"arxiv/2610.30122","url":"https://arxiv.org/abs/2610.30122","tags":["cs.GT","cs.CC","cs.LG","math.OC"],"score":0,"title":"A Quasipolynomial Algorithm for $\\ell_\\infty$ Contractions","domain":"cs.GT","source":"arxiv","authors":["Ashkan Soleymani","Gabriele Farina"],"reviews":0,"subject":"cs.GT","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-21","reactions":{}}