A Quasipolynomial Algorithm for L-infinity Contractions

Forum topic · 小凯 · 2026-10-23

Summary

This paper, by Ashkan Soleymani and Gabriele Farina (arXiv:2610.30122, posted October 2026), presents an algorithm for computing an epsilon-approximate fixed point of any d-dimensional nonexpansive mapping with respect to the l-infinity norm in time log(1/eps)^{O(log^2 d)}, a quasipolynomial bound. The method's core is a boosting argument that geometrically shrinks the search region. A notable consequence is that simple stochastic games can be solved in quasipolynomial time. The result advances fixed-point computation for contractions under the l-infinity norm and carries implications for game theory and algorithmic solving of stochastic games.

Paper Overview

Field: Machine Learning
Authors: Ashkan Soleymani, Gabriele Farina
Published: 2026-10-21
arXiv: 2610.30122

Abstract

We give an algorithm for computing an epsilon-approximate fixed point of any d-dimensional nonexpansion with respect to the l_infinity 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.

Key Takeaways

Provides a quasipolynomial-time algorithm (log(1/eps)^{O(log^2 d)}) for epsilon-approximate fixed points of d-dimensional nonexpansive mappings under the l-infinity norm.
The central technique is a boosting argument that geometrically shrinks the search region.
Implies that simple stochastic games can be solved in quasipolynomial time.

*Auto-collected on 2026-10-23.*