arXiv:2611.01302 · v1
A Decomposition Theorem and a Simple Algorithm for Contraction Fixed Points
摘要
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.
作者备注：To appear in SOSA 2027. This paper subsumes some of the results in our earlier preprint arXiv:2602.10296. This manuscript is an August 2026 snapshot, predating OpenAI's list of papers and the subsequent developments. The discussion and references have been retained as of that date