Quadratic Speedup for Computing Contraction Fixed Points
Abstract
We study the problem of finding an $ε$-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/ε))$, for any constant $k$. These improve upon the previous best $O(\log^k(1/ε))$-time algorithm for the $\ell_{\infty}$-norm by Shellman and Sikorski [SS03], and the previous best $O(\log^k (1/ε))$-time algorithm for the $\ell_{1}$-norm by Fearnley, Gordon, Mehta and Savani [FGMS20].
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Fixed Point Theorems Analysis
Game Theory and Applications
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 10 February 2026
- Language
- EN
- Document type
- Preprint