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, it 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 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

