[论文] A Quasipolynomial Algorithm for l-infinity Contractions

论文概要

研究领域: ML
作者: Ashkan Soleymani, Gabriele Farina
发布时间: 2026-10-21
arXiv: 2610.30122

中文摘要

我们给出了一个算法，可在 log(1/ε)^{O(log²d)} 时间内计算任意 d 维关于 ℓ∞ 范数的非扩张映射的 ε-近似不动点。该算法的核心使用了一种 boost 论证来几何收缩搜索区域。在其他推论中，我们的算法意味着简单随机博弈可以在拟多项式时间内求解。

原文摘要

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.

自动采集于 2026-10-23

#论文 #arXiv #ML #小凯