Background
----------


At the risk of greatly oversimplifying matters, let me state a heuristic from Granas and Dugundji's beautiful [book](http://rads.stackoverflow.com/amzn/click/0387001735): *fixed point theorems fall into two broad categories*. The first class is usually functional analytic and imposes strong conditions on the *map* $f:X \to X$ whereas the second class is usually algebraic topological and imposes strong conditions on the *space* $X$ itself.


A typical example of the first class of theorems is the [fixed point theorem of Banach](http://en.wikipedia.org/wiki/Banach_fixed-point_theorem). While the spaces it applies to are fairly general (complete metric spaces), the function must have a Lipschitz constant strictly less than $1$. On the other hand, [Brouwer's theorem](http://en.wikipedia.org/wiki/Brouwer_fixed-point_theorem) falls into the second class. Any continuous map works, but the domain must be a compact and convex subset of Euclidean space (originally a disk). Of course, both these theorems have been *vastly* generalized from the versions that I am stating here.


Question
--------


One fundamental advantage of the Banach theorem is that it actually provides a recipe for converging to the fixed point as part of the standard proof: just start at an initial point and iterate. The proofs of the Brouwer theorem that I have seen do no such thing. The best known proof (I think) is the one by contradiction: assuming the domain is a disk, if $f(x)$ and $x$ are always distinct then the ray from $f(x)$ through $x$ to the boundary of said disk provides a deformation-retraction from the disk to its boundary, aha!


Here is my question:



> 
> Is there any way to actually find a fixed point when using Brouwer's theorem?
> 
> 
> 


A Possible Idea
---------------


One scheme that unfortunately fails is as follows. Consider the sequence of iterates $f^n(x)$ for $n \in \mathbb{N}$ and any initial $x$ in the domain. We have an infinite sequence in a compact set, and hence a convergent subsequence, so the limit point is a candidate. This won't work since **a**) we haven't used convexity at all, and **b**) one may just be converging to a periodic orbit of $f$. 



Can we actually find any fixed points with Brouwer's theorem?
The paper "Exponential lower bounds for finding Brouwer fixed points"


*Addendum by original poster:* It was non-trivial to find a copy of this great paper of Hirsch, Papadimitriou and Vavasis. It does answer my general question quite clearly: finding Brouwer fixed points is exponentially hard in the worst case no matter what algorithm you use. [Here](https://dl.dropbox.com/u/74531549/HPVBrouwer.pdf) is a link to this paper for all those who are interested and don't want to run into many, many pay-walls. I will take it down in a few days. -VN


