Quadratic Speedup for Computing Contraction Fixed Points

Xi Chen, Yuhao Li, Mihalis Yannakakis

We study the problem of finding an $\epsilon$-fixed point of a contraction map $f:[0,1{]}^k\mapsto [0,1{]}^k$ under both the ${\ell }_{\infty }$-norm and the ${\ell }_1$-norm. For both norms, we give a…