Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-057 | 28th March 2024 02:23

Computing a Fixed Point of Contraction Maps in Polynomial Queries

RSS-Feed




TR24-057
Authors: Xi Chen, Yuhao Li, Mihalis Yannakakis
Publication: 31st March 2024 09:18
Downloads: 269
Keywords: 


Abstract:

We give an algorithm for finding an $\epsilon$-fixed point of a contraction map $f:[0,1]^k\rightarrow [0,1]^k$ under the $\ell_\infty$-norm with query complexity $O (k^2\log (1/\epsilon ) )$.



ISSN 1433-8092 | Imprint