Computer Science – Computer Science and Game Theory
Scientific paper
2007-02-16
Computer Science
Computer Science and Game Theory
Scientific paper
In 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}).
Chen Xi
Teng Shang-Hua
No associations
LandOfFree
Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-196289