A converse to Banach's fixed point theorem and its CLS-completeness

DOI10.1145/3188745.3188968zbMath1493.47067arXiv1702.07339OpenAlexW2591713661MaRDI QIDQ5230275

Constantinos Daskalakis, Manolis Zampetakis, Christos Tzamos

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1702.07339

zbMATH Keywords

computational complexityglobal convergenceconvergence ratepower methodcontraction mapsBessaga's theoremBanach's theoremCLS-completeness

Mathematics Subject Classification ID

Fixed-point theorems (47H10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (9)

Secure fast evaluation of iterative methods: with an application to secure PageRank ⋮ Unique end of potential line ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ The Hairy Ball problem is PPAD-complete ⋮ On the complexity of finding a Caristi's fixed point ⋮ The complexity of the parity argument with potential ⋮ Unique End of Potential Line ⋮ The Hairy Ball Problem is PPAD-Complete. ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

This page was built for publication: A converse to Banach's fixed point theorem and its CLS-completeness