Exponential lower bounds for finding Brouwer fixed points (Q911230)

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.