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

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