Quadratic Speedup for Computing Contraction Fixed Points

Abstract

We study the problem of finding an $\hat{I}\mu$-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 an algorithm with running time $O({\log }^{\lceil k/2\rceil }(1/\hat{I}\mu ))$, for any constant $k$. These improve upon the previous best $O({\log }^k(1/\hat{I}\mu ))$-time algorithm for the ${\ell }_{\infty }$-norm by Shellman and Sikorski [SS03], and the previous best $O({\log }^k(1/\hat{I}\mu ))$-time algorithm for the ${\ell }_1$-norm by Fearnley, Gordon, Mehta and Savani [FGMS20].