A Quasipolynomial Algorithm for $\ell_\infty$ Contractions
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.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper presents a quasipolynomial-time algorithm for computing approximate fixed points of $\ell_\infty$-contractions, resolving a major open problem in the complexity of simple stochastic games. By introducing a novel boosting-based geometric search strategy, the authors improve the running time from subexponential to quasipolynomial, providing a significant theoretical advance with broad implications for game theory, verification, and optimization.
Methodology
The paper introduces a deterministic algorithm for computing $\epsilon$-approximate fixed points of $\ell_\infty$-contractions in quasipolynomial time, specifically $\log(1/\epsilon)^{O(\log^2 d)}$. The core innovation is a "boosting" argument applied to a geometric search problem. The authors define a "thin labeling" subroutine that recursively splits dimensions based on median side lengths to identify which faces of a search box can be safely shrunk. They then amplify the accuracy of these thin labelings using a technique analogous to AdaBoost, treating the labeling problem as an extremal amplification game. This approach cleverly reduces the subexponential dependence on dimension $d$ found in prior work (Feodorov and Haslebacher) to a quasipolynomial dependence. The theoretical framework is rigorous, with detailed proofs of the potential functions and correctness of the boosting steps.
Results & evaluation
As a purely theoretical computer science and optimization paper, there are no empirical experiments, datasets, or benchmark comparisons. The "evaluation" is entirely analytical, proving tight bounds on the number of arithmetic operations and function evaluations required. The significance is derived from the theoretical breakthrough in complexity bounds rather than empirical performance.
Reproducibility
The algorithm is described in full pseudocode (Algorithms 1, 2, 3, 4). The theoretical guarantees are proven rigorously. However, without code or empirical benchmarks, "reproducibility" in the practical sense is limited to the ability of other theorists to verify the proofs. The unit-cost real machine model is used for analysis, which is standard in this field but limits direct practical implementation without bit-complexity analysis (which is noted as straightforward but not fully detailed).
Limitations
The algorithm is deterministic and applies to $\ell_\infty$ norms. While it solves Simple Stochastic Games (SSGs) in quasipolynomial time, it does not resolve the open question of whether SSGs are in P. The quasipolynomial bound, while a significant improvement over subexponential, is still super-polynomial, meaning it may not be practical for very large dimensions or high-precision requirements. The paper focuses on the worst-case complexity; smoothed analysis or average-case performance is not addressed.
Broader impact
This result has significant implications for the complexity of several fundamental problems in game theory and verification, including Simple Stochastic Games, stochastic parity games, mean-payoff games, and modal $\mu$-calculus model checking. By providing a quasipolynomial-time algorithm for these problems, it advances the state of the art in understanding the computational hardness of these decision problems. It also contributes to the broader field of fixed-point computation, which is central to reinforcement learning (value iteration) and distributed computing. The use of boosting for geometric search is a novel methodological contribution that could inspire further research in algorithmic game theory. The paper presents a quasipolynomial-time algorithm for computing approximate fixed points of $\ell_\infty$-contractions, resolving a major open problem in the complexity of simple stochastic games. By introducing a novel boosting-based geometric search strategy, the authors improve the running time from subexponential to quasipolynomial, providing a significant theoretical advance with broad implications for game theory, verification, and optimization.
Author of this paper? Send a correction.