Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation
<|reference_start|>Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation: 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}).<|reference_end|>
@article{chen2007paths,
    title={Paths Beyond Local Search: A Nearly Tight Bound for Randomized
  Fixed-Point Computation},
    author={Xi Chen and Shang-Hua Teng},
    journal={arXiv preprint arXiv:cs/0702088},
    year={2007},
    archivePrefix={arXiv},
    eprint={cs/0702088},
    primaryClass={cs.GT}
}