Subexponential algorithm improves solving contraction fixed points
A Decomposition Theorem and a Simple Algorithm for Contraction Fixed Points
Computational ComplexityData Structures and Algorithms
Summary
Finding fixed points in math functions is a common problem in computer science. This paper presents a way to break down such problems into simpler parts, making it easier to find approximate fixed points efficiently. The authors also show a new method to speed up existing algorithms, making them much faster for high-dimensional problems. As a bonus, their approach helps solve related game theory problems that were previously harder to tackle quickly.
What this means in practice
- •For game theory software developers: Enable faster deterministic algorithms for solving simple stochastic and mean-payoff games, improving strategic game analysis.
- •For optimization engineers: Implement more efficient contraction fixed point calculations in high-dimensional optimization problems, reducing computation time.
A theory result. No direct application yet.
Authors
Xi Chen, Yuhao Li, Mihalis Yannakakis
Abstract
We prove a decomposition theorem for the problem of computing an approximate fixed point of a contraction map $f\colon [0,1]^k \to [0,1]^k$ under the $\ell_{\infty}$-norm. After a preliminary version of the decomposition theorem appeared on arXiv [CLY26], Feodorov and Haslebacher [FH26] gave a striking application of the theorem, showing that it can be used to convert any $\operatorname{poly}(k,\log(1/\varepsilon))$-query algorithm with running time $(k\log(1/\varepsilon))^{O(k)}$ into an algorithm with running time $(k\log(1/\varepsilon))^{O(\sqrt{k})}$. They instantiated this framework with an $O(k^2\log(1/\varepsilon))$-query algorithm with the desired running time, thereby obtaining the first subexponential-time algorithm for contraction fixed points under the $\ell_{\infty}$-norm and, via well-known reductions, the first deterministic subexponential-time algorithm for simple stochastic games and mean-payoff games. In addition to the decomposition theorem, as our second main result in this paper, we show that the $O(k\log(1/\varepsilon))$-query algorithm of [CLY25] can be implemented in time $(k\log(1/\varepsilon))^{O(k)}$; our algorithm may be viewed as conceptually simpler compared to the algorithm of [FH26]. A key observation here is that the function constructed in [CLY25], whose fixed points are used as the next query points, turns out to be nonexpansive under the $\ell_{\infty}$-norm, so the brute-force procedure can be replaced by known algorithms for contraction fixed points.