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

Simple item page
dc.creatorChen, Xi
dc.creatorTeng, Shang-Hua
dc.date2007-02-16
dc.date.accessioned2026-07-07T07:47:17Z
dc.date.available2026-07-07T07:47:17Z
dc.descriptionIn 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over [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 this open 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 paper, we give a nearly-tight bound of Omega(n)^{d-1} on the randomized query complexity for computing a fixed point of a discrete Brouwer function over [1:n]^d. 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 query model; the deterministic complexity of this problem is Theta (n^{d-1}).
dc.identifierhttps://arxiv.org/abs/cs/0702088
dc.identifierhttp://arxiv.org/abs/cs/0702088
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/124114
dc.subjectComputer Science and Game Theory
dc.subjectF.1.2; F.1.3
dc.titlePaths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation
dc.typetext

Files

Collections

arXiv