Abstract
We give an algorithm for finding an $\epsilon$-fixed point of a contraction map $f:[0,1]^k\mapsto[0,1]^k$ under the $\ell_\infty$-norm with query complexity $O (k\log (1/\epsilon ) )$.
Computing a Fixed Point of Contraction Maps in Polynomial Queries
Related papers
Ranked by semantic similarity β how closely each paper's abstract matches this one (100% = near-identical topic).
- Quadratic Speedup for Computing Contraction Fixed Points (2026)85% match
- Faster Approximate Fixed Points of $\ell_Δ±nfty$-Contractions (2026)76% match
- Fixed Point Computation: Beating Brute Force with Smoothed Analysis (2025)64% match
- The Mystery Deepens: On the Query Complexity of Tarski Fixed Points (2026)60% match
- A Single Exponential-Time FPT Algorithm for Cactus Contraction (2025)59% match
- Learning to accelerate Krasnosel'skii-Mann fixed-point iterations with guarantees (2026)55% match
- Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps (2023)55% match
- ARRIVAL: Recursive Framework & $\ell_1$-Contraction (2025)54% match