The authors study maps f:[0,1]^d -> [0,1]^d that are (1-gamma)-contractions in the ell_infty norm.
Quasipolynomial algorithm finds approximate fixed points of ell_infty contractions
Soleymani and Farina reduce the running time for ell_infty contractions from subexponential to quasipolynomial, yielding quasipolynomial-time algorithms for simple stochastic games.
Top University
Ashkan Soleymani · Gabriele Farina
MIT
Research Digest··2 min read
Soleymani and Farina give a deterministic algorithm that computes an epsilon-near fixed point of any d-dimensional ell_infty contraction in time log(1/epsilon)^{O(log^2 d)}.
§