Exponential lower bounds for finding Brouwer fixed points

DOI10.1016/0885-064X(89)90017-4zbMath0696.65045OpenAlexW2017781790MaRDI QIDQ911230

Stephen A. Vavasis, Michael D. Hirsch, Christos H. Papadimitriou

Publication date: 1989

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0885-064x(89)90017-4

zbMATH Keywords

upper boundslower boundsfunction evaluationsbisection algorithmcomplexity of fixed point algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Fixed-point theorems (47H10) Fixed-point and coincidence theorems (topological aspects) (54H25) Fixed points and coincidences in algebraic topology (55M20) Nonlinear algebraic or transcendental equations (65H99)

Related Items (29)

Inapproximability of Nash Equilibrium ⋮ On the complexity of the parity argument and other inefficient proofs of existence ⋮ A recursive algorithm for the infinity-norm fixed point problem ⋮ Computing equilibria: a computational complexity perspective ⋮ Quantum separation of local search and fixed point computation ⋮ Communication complexity of approximate Nash equilibria ⋮ Existence and computation of short-run equilibria in economic geography ⋮ Application of Canonical Duality Theory to Fixed Point Problem ⋮ Unique end of potential line ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Understanding PPA-completeness ⋮ General equilibrium models and homotopy methods ⋮ Equilibria, fixed points, and complexity classes ⋮ Nash equilibria: complexity, symmetries, and approximation ⋮ A note on two fixed point problems ⋮ Circumscribed ellipsoid algorithm for fixed-point problems ⋮ On modeling and complete solutions to general fixpoint problems in multi-scale systems with applications ⋮ Optimal bounds on finding fixed points of contraction mappings ⋮ A two-dimensional bisection envelope algorithm for fixed points ⋮ Imitation games and computation ⋮ Multiple-source adaptation theory and algorithms ⋮ Can PPAD hardness be based on standard cryptographic assumptions? ⋮ An impossibility theorem for price-adjustment mechanisms ⋮ A simplicial approach for discrete fixed point theorems ⋮ Unique End of Potential Line ⋮ On the complexity of 2D discrete fixed point problem ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ A class of ``onto multifunctions ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Uses Software

• PLALGO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal solution of nonlinear equations satisfying a Lipschitz condition
• Complexity of fixed points. I
• Computational complexity of real functions
• On the average number of steps of the simplex method of linear programming
• Computational complexity of complementary pivot methods
• Homotopies for computation of fixed points
• On the computational complexity of piecewise-linear homotopy algorithms
• Equilibrium Points of Bimatrix Games
• Bimatrix Equilibrium Points and Mathematical Programming
• The Approximation of Fixed Points of a Continuous Mapping
• SIMPLICIAL APPROXIMATION OF FIXED POINTS
• Equilibrium points in n -person games
• On Some Systems of Equations of Mathematical Economics
• Existence of an Equilibrium for a Competitive Economy

This page was built for publication: Exponential lower bounds for finding Brouwer fixed points