Newest papers

A Quasipolynomial Algorithm for $\ell_\infty$ Contractions

Ashkan Soleymani, Gabriele Farina · 2026 · arXiv

DOI: 10.48550/arXiv.2610.30122 · open-access PDF

Vietnamese

Chúng tôi cung cấp một thuật toán để tính toán một điểm cố định khoảng $\eps$ của bất kỳ $d$-dimensional nonexpansion liên quan đến $\ell_\infty$ chuẩn trong thời gian $\log(1/\eps)^O{O(\log^2 d)}$. Tại cốt lõi của nó, phương pháp của chúng tôi sử dụng một lập luận tăng cường để thu hẹp một khu vực tìm kiếm theo hình học.

Machine translation (Meta M2M100); the English original follows.

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.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange