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 (nd-1) to O (nd/2). It remains open whether randomization helps fixed-point computation. Inspired by this problem and recent advances on equilibrium computation, we have been fascinated by the following question: Is a fixed-point or an equilibrium fundamentally harder to find than a local optimum? In this talk, I will present a tight bound of (Ω(n))d-1 on the randomized query complexity for computing a fixed point of a discrete Brouwer function over grid [1:n]d. Since the randomized query complexity of global optimization over [1:n]d is Theta (nd), the randomized query model 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 in fixed-point computation in the query model, as its deterministic complexity is also Theta (nd-1). This is a joint work with Xi Chen of Tsinghua University.
©2007 Microsoft Corporation. All rights reserved.
