Computing a fixed point of contraction maps in polynomial queries

DOI10.1145/3744738MaRDI QIDQ6912096zbMATH OpenFDO

Authors Xi Chen, Yu-Hao Li, Mihalis Yannakakis

Publication date 23 October 2025

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3744738

zbMATH Keywords

contraction fixed pointquery complexityTFNP

Mathematics Subject Classification ID

Fixed-point and coincidence theorems (topological aspects) (54H25) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Cites work

• 2-D Tucker is PPA complete
• A converse to Banach's fixed point theorem and its CLS-completeness
• A recursive algorithm for the infinity-norm fixed point problem
• A two-dimensional bisection envelope algorithm for fixed points
• An ellipsoid algorithm for the computation of fixed points
• Approximating fixed points of weakly contracting mappings
• Contraction Mappings in the Theory Underlying Dynamic Programming
• Deciding Parity Games in Quasi-polynomial Time
• Exponential lower bounds for finding Brouwer fixed points
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• How easy is local search?
• scientific article; zbMATH DE number 3128787 (Why is no real title available?)
• scientific article; zbMATH DE number 3148886 (Why is no real title available?)
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• scientific article; zbMATH DE number 3109695 (Why is no real title available?)
• Matching algorithmic bounds for finding a Brouwer fixed point
• On the complexity of 2D discrete fixed point problem
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of the parity argument and other inefficient proofs of existence
• Optimal solution of nonlinear equations
• Stochastic Games
• Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales.
• The complexity of gradient descent: CLS = PPAD pls
• The complexity of mean payoff games on graphs
• The complexity of stochastic games
• The imbedding problem for Riemannian manifolds
• Understanding PPA-completeness
• Unique end of potential line
• White-box vs. black-box complexity of search problems: Ramsey and graph property testing
• Zum Einbettungssatz von J. Nash

This page was built for publication: Computing a fixed point of contraction maps in polynomial queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6912096)