Quadratic Speedup for Computing Contraction Fixed Points

arXiv:2602.10296v1 Announce Type: new
Abstract: We study the problem of finding an $epsilon$-fixed point of a contraction map $f:[0,1]^kmapsto[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/2rceil}(1/epsilon))$, for any constant $k$. These improve upon the previous best $O(log^k(1/epsilon))$-time algorithm for the $ell_{infty}$-norm by Shellman and Sikorski [SS03], and the previous best $O(log^k (1/epsilon ))$-time algorithm for the $ell_{1}$-norm by Fearnley, Gordon, Mehta and Savani [FGMS20].