Computing a Fixed Point of Contraction Maps in Polynomial Queries

March 29, 2024 ยท The Ethereal ยท ๐Ÿ› Journal of the ACM

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Xi Chen, Yuhao Li, Mihalis Yannakakis arXiv ID 2403.19911 Category cs.CC: Computational Complexity Cross-listed cs.DS, cs.GT Citations 0 Venue Journal of the ACM Last Checked 3 months ago
Abstract
We give an algorithm for finding an $ฮต$-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/ฮต) )$.
Community shame:
Not yet rated
๐Ÿ“„ View on arXiv ๐ŸŒ View on ar5iv ๐Ÿ“‘ PDF ๐ŸŽ‰ Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Computational Complexity