pipette
ESEspañol

A Quasipolynomial Algorithm for Contractions

Ashkan Soleymani, Gabriele Farina

Preprint

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.