2007/02/16 by Xi Chen, Shang‐Hua Teng, Chen, Xi +1
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computer Science and Game Theory (cs.GT) #F.1.2 #F.1.3 #FOS: Computer and information sciences #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.cs/0702088
openalex publication_date 2007/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (nd-1) to O (d1/2nd/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 (nd), 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 (nd-1).