A Quasipolynomial Algorithm for Contractions
In the authors' words
We give an algorithm for computing an -approximate fixed point of any -dimensional nonexpansion with respect to the norm in time . 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.
Main resultThe abstract does not state a limitation.
Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.