In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over grid [1 : n](d) from Theta(n(d-1)) to O (d(1/2)n(d/2)). It remains open whether randomization helps fixed-point computation. Inspired by the recent advances on the complexity of equilibrium computation, we solve this open problem by giving an asymptotically tight bound of (Omega (n))(d-1) on the randomized query complexity for computing a fixed point of a discrete Brouwer function over grid [1 : n](d). Our result can be extended to the black-box query model for Sperner's Lemma in any dimension. It also yields a tight bound for the computation of d-dimensional approximate Brouwer fixed points as defined by Scarf and by Hirsch, Papadimitriou, and Vavasis. Since the randomized query complexity of global optimization over [1 : n]d is Theta(n(d)), the randomized query model over [1 : n](d) strictly separates these three important search problems: Global optimization is harder than fixed-point computation, and fixed-point computation is harder than local search. Our result indeed demonstrates that randomization does not help much in fixed-point computation in the black-box query model. Our randomized lower bound matches the deterministic complexity of this problem, which is Theta (n(d-1)).
