A Quasipolynomial Algorithm for $ell_infty$ Contractions

Özetle: 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)}$.

Özet

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.

Orijinal Özet (İngilizce)

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.

Kaynak: arXiv:2610.30122 · PDF