Computing a Fixed Point of Contraction Maps in Polynomial Queries
<|reference_start|>Computing a Fixed Point of Contraction Maps in Polynomial Queries: 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^2\log (1/\epsilon ) )$.<|reference_end|>
@article{chen2024computing,
    title={Computing a Fixed Point of Contraction Maps in Polynomial Queries},
    author={Xi Chen, Yuhao Li, Mihalis Yannakakis},
    journal={arXiv preprint arXiv:2403.19911},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.19911},
    primaryClass={cs.CC cs.DS cs.GT}
}