Exponential lower bounds for finding Brouwer fixed points
From MaRDI portal
The authors consider algorithms for computing fixed points which use only function evaluations. In one dimension, the bisection algorithm can compute an approximate fixed-point of a map \(f\) (i.e. a point x, such that \(| x-f(x)| \leq 2^{-p})\) in essentially \(O(p)\) steps. No such algorithm exists in two or more dimensions. This is demonstrated by explicitly constructing a map \(f\) for any algorithm such that the number of steps will be exponential in \(p\) and in the dimension of the space. These lower bounds are compared to known upper bounds and are shown to be of the same or similar order.
Recommendations
Cites work
- Bimatrix Equilibrium Points and Mathematical Programming
- Complexity of fixed points. I
- Computational complexity of complementary pivot methods
- Computational complexity of real functions
- Equilibrium points in n -person games
- Equilibrium Points of Bimatrix Games
- Existence of an Equilibrium for a Competitive Economy
- Homotopies for computation of fixed points
- scientific article; zbMATH DE number 3827201 (Why is no real title available?)
- scientific article; zbMATH DE number 3466805 (Why is no real title available?)
- scientific article; zbMATH DE number 3487169 (Why is no real title available?)
- On Some Systems of Equations of Mathematical Economics
- On the average number of steps of the simplex method of linear programming
- On the computational complexity of piecewise-linear homotopy algorithms
- Optimal solution of nonlinear equations satisfying a Lipschitz condition
- SIMPLICIAL APPROXIMATION OF FIXED POINTS
- The Approximation of Fixed Points of a Continuous Mapping
Cited in
(41)- A simplicial approach for discrete fixed point theorems
- On the complexity of 2D discrete fixed point problem
- Condition-sensitive computation of approximate fixed points
- A class of ``onto multifunctions
- On the complexity of the parity argument and other inefficient proofs of existence
- A recursive algorithm for the infinity-norm fixed point problem
- General equilibrium models and homotopy methods
- On modeling and complete solutions to general fixpoint problems in multi-scale systems with applications
- Multiple-source adaptation theory and algorithms
- Unique end of potential line
- Understanding PPA-completeness
- A note on two fixed point problems
- Application of Canonical Duality Theory to Fixed Point Problem
- Circumscribed ellipsoid algorithm for fixed-point problems
- An impossibility theorem for price-adjustment mechanisms
- The Brouwer fixed point theorem revisited
- Matching algorithmic bounds for finding a Brouwer fixed point
- Inapproximability of Nash equilibrium
- Equilibria, fixed points, and complexity classes
- Nash equilibria: complexity, symmetries, and approximation
- Complexity of fixed point computation
- scientific article; zbMATH DE number 927048 (Why is no real title available?)
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- Unique End of Potential Line
- Hardness of continuous local search: query complexity and cryptographic lower bounds
- Can PPAD hardness be based on standard cryptographic assumptions?
- A Faster Algorithm for Finding Tarski Fixed Points
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- Computations and complexities of Tarski's fixed points and supermodular games
- Envy-free cake-cutting for four agents
- Computing a fixed point of contraction maps in polynomial queries
- The randomized query complexity of finding a Tarski fixed point on the Boolean hypercube
- Computations and complexities of Tarski's fixed points and supermodular games
- A two-dimensional bisection envelope algorithm for fixed points
- Computing approximate roots of monotone functions
- Tarski lower bounds from multi-dimensional herringbones
- Computing equilibria: a computational complexity perspective
- Quantum separation of local search and fixed point computation
- Existence and computation of short-run equilibria in economic geography
- Optimal bounds on finding fixed points of contraction mappings
- Imitation games and computation
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)
