A Quasipolynomial Algorithm for $\ell_\infty$ Contractions

Ashkan Soleymani, Gabriele Farina

Oct 21, 2026arXiv:2610.30122v1

cs.GTcs.CCcs.LGmath.OC

Scorecard· 16/16

8.5/10 impact

First quasipolynomial algorithm for general ℓ∞-contraction fixed points, implying quasipolynomial SSGs; surprising boosting technique on a central open problem, though not polynomial and impractical.

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.

AI Impact Assessments

(1 model)

Core Contribution

The paper gives the first quasipolynomial-time algorithm, log(1/ε)^{O(log² d)}, for computing an ε-approximate fixed point of an arbitrary ℓ∞-contraction or nonexpansion. The previous best, by Feodorov–Haslebacher, was log(1/ε)^{O(√d log d)}, which is subexponential. Because simple stochastic games (SSGs) reduce to this problem with polynomial-bit parameters, the result gives the first quasipolynomial-time algorithm for SSGs. By Andersson–Miltersen equivalences it also covers turn-based stochastic parity, mean-payoff, and discounted games. It gives quasipolynomial approximation of Shapley's concurrent discounted games, whose value operators are not monotone.

The technique has two parts:

1. Thin labeling. Split coordinates by median box side length and recursively solve two half-dimensional contractions. This yields a labeling that identifies which faces are closest to or farthest from x*, but only with very small accuracy (~γη).

2. Boosting. The thin labeler is treated as a weak learner in an "extremal amplification game". An AdaBoost-style potential argument with exponential weights and a recursion over accuracy scales amplifies the accuracy to a constant fraction of the box side. The cube then shrinks by 7/8 per iteration.

The cost of boosting is quasipolynomial in log(κ/ρ). That is why the running time depends only on log(1/γε) rather than on 1/γ.

The conceptual novelty is using boosting as an algorithmic primitive in geometric fixed-point computation. This is an unexpected import from learning theory. The amplification game is cleanly abstracted and independent of geometry.

Methodological Rigor

This is a theory paper with complete proofs.

The ThinLabel lemma uses a careful case analysis on the coordinate attaining the max error, covering narrow, wide, and median coordinates, plus the clipping effects. It looks correct.

The Amplify correctness argument is an intricate induction. It uses the contract, light versus heavy iterations, and the product-of-bounds termination (Lemma 3).

The cost recurrence is solved with a binomial bound. The final recurrence unrolling in Theorem 1 is somewhat terse about constants, but the structure (depth log d, with k ≤ Ct and h ≤ Crℓ) is plausible.

The model is a unit-cost real machine, with bit complexity asserted as "straightforward".

Concerns: the proof is dense, and some steps (the invariance of δ ranges and the claim in (9)) require careful checking. Given the elegant recursion and the standard potential argument, errors seem unlikely, but full verification is nontrivial. No experiments are given, and none are needed.

Potential Impact

It is a major advance on a central open problem. Whether SSGs, mean-payoff games, and parity games are in P is a long-standing question. Quasipolynomial-time parity games (Calude et al. 2017) were a landmark. This result gives a unified route for the stochastic setting, which was not previously known to be in quasipolynomial time.

It applies to arbitrary nonexpansive maps with no monotonicity or explicit game structure. It is also a black-box algorithm that needs only function evaluations.

Techniques likely to be reused include median-split recursion combined with boosting amplification, extension to ℓp norms, and extension to other fixed-point classes such as Tarski and UEOPL-type problems. It narrows the gap to polynomial time and may spur either a polynomial algorithm or hardness-type evidence.

The related-work section notes concurrent OpenAI preprints on quasipolynomial algorithms for deterministic and stochastic mean-payoff games. These exploit monotonicity. This reduces the exclusivity of the SSG and mean-payoff consequences, but the present result is more general and structurally different.

Practical impact is low. The exponent log² d with large constants (129^k branching) makes the algorithm impractical. The significance is theoretical.

Timeliness

Fixed-point computation of contractions has seen a burst of progress (CLY24, CLY25, FH26, BFG+25, HLSW25, DFZ27). The paper takes the headline problem from subexponential to quasipolynomial. It is directly relevant to algorithmic game theory, stochastic games, and verification. The acknowledgments note AI assistance in exploring ideas, which is mildly notable for the field but does not affect the technical content.

Strengths

It makes a large leap in the exponent, from √d log d to log² d.

The boosting idea is novel in this context, and the extremal amplification abstraction is clean and likely reusable.

It is deterministic and general: it needs no monotonicity and no access to the game structure.

It has many downstream consequences (the Figure 1 hierarchy).

The writing is clear for such a technical result. It includes intuition, a naive baseline, and a vanilla-boosting primer.

Limitations

It is still not polynomial, so the central open problem remains open.

The algorithm is impractical, with huge constants and branching.

The proof is delicate. Verifying Lemma 4 and the recurrence takes effort.

Bit complexity is not analyzed in detail.

Parity games already had quasipolynomial algorithms, and concurrent work covers mean-payoff games. The unique new consequences are for stochastic turn-based games and Shapley games.

Query complexity is not improved. The algorithm's evaluation count is also quasipolynomial, versus O(d log(1/ε)) for CLY, though CLY has exponential computation.

Overall

This is a strong theoretical result at the top of the algorithmic game theory and fixed-point literature, comparable in spirit to a STOC/FOCS best-paper candidate. It resolves a major gap with a surprising technique, and its reuse potential is high within theory.

Rating:8.5/ 10

Significance 8.5Rigor 8Novelty 8.5Clarity 7.5

Generated Oct 22, 2026

Comparison History (0)

No comparisons yet.