Exponential lower bounds for finding Brouwer fixed points
DOI10.1016/0885-064X(89)90017-4zbMATH Open0696.65045OpenAlexW2017781790MaRDI QIDQ911230FDOQ911230
Authors: M. Hirsch, Stephen A. Vavasis, Christos 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
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Equilibrium points in n -person games
- Title not available (Why is that?)
- Bimatrix Equilibrium Points and Mathematical Programming
- Existence of an Equilibrium for a Competitive Economy
- On Some Systems of Equations of Mathematical Economics
- Equilibrium Points of Bimatrix Games
- The Approximation of Fixed Points of a Continuous Mapping
- Homotopies for computation of fixed points
- SIMPLICIAL APPROXIMATION OF FIXED POINTS
- Computational complexity of complementary pivot methods
- Computational complexity of real functions
- Title not available (Why is that?)
- On the average number of steps of the simplex method of linear programming
- Optimal solution of nonlinear equations satisfying a Lipschitz condition
- Complexity of fixed points. I
- On the computational complexity of piecewise-linear homotopy algorithms
Cited In (35)
- Hardness of continuous local search: query complexity and cryptographic lower bounds
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- Optimal bounds on finding fixed points of contraction mappings
- Complexity of fixed point computation
- On modeling and complete solutions to general fixpoint problems in multi-scale systems with applications
- A two-dimensional bisection envelope algorithm for fixed points
- Nash equilibria: complexity, symmetries, and approximation
- Quantum separation of local search and fixed point computation
- A simplicial approach for discrete fixed point theorems
- Communication complexity of approximate Nash equilibria
- Understanding PPA-completeness
- Inapproximability of Nash equilibrium
- Application of Canonical Duality Theory to Fixed Point Problem
- Can PPAD hardness be based on standard cryptographic assumptions?
- Unique End of Potential Line
- On the complexity of the parity argument and other inefficient proofs of existence
- General equilibrium models and homotopy methods
- Condition-sensitive computation of approximate fixed points
- Equilibria, fixed points, and complexity classes
- Unique end of potential line
- A class of ``onto multifunctions
- Imitation games and computation
- A recursive algorithm for the infinity-norm fixed point problem
- On the complexity of 2D discrete fixed point problem
- Existence and computation of short-run equilibria in economic geography
- The Brouwer fixed point theorem revisited
- Title not available (Why is that?)
- Matching algorithmic bounds for finding a Brouwer fixed point
- Circumscribed ellipsoid algorithm for fixed-point problems
- An impossibility theorem for price-adjustment mechanisms
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- Multiple-source adaptation theory and algorithms
- Computing equilibria: a computational complexity perspective
- A Faster Algorithm for Finding Tarski Fixed Points
- A note on two fixed point problems
Uses Software
This page was built for publication: Exponential lower bounds for finding Brouwer fixed points
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911230)
