Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation

Опубликовано 6 сентября 2016, 16:26

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 (n^{d/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 (\Omega(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 (n^{d}), 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 (n^{d-1}). This is a joint work with Xi Chen of Tsinghua University.