A Quasipolynomial Algorithm for $\ell_\infty$ Contractions
The algorithm implies that simple stochastic games can be solved in quasipolynomial time.
Ashkan Soleymani and Gabriele Farina give a method for computing an ε-approximate fixed point of any d-dimensional nonexpansion under the ℓ∞ norm. Its running time is $\log(1/\varepsilon)^{O(\log^2 d)}$. The method uses a boosting argument to geometrically shrink the search region.
ArXiv · AI/CL/LG's note
Ashkan Soleymani and Gabriele Farina give a method for computing an ε-approximate fixed point of any d-dimensional nonexpansion under the ℓ∞ norm. Its running time is $\log(1/\varepsilon)^{O(\log^2 d)}$. The method uses a boosting argument to geometrically shrink the search region.
ArXiv · AI/CL/LG's note
score 5