Paths Beyond Local Search: A 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 grid 1:n]d from Theta (nd-1) to O (nd/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 (Ω(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 (nd), 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 (nd-1).
This is a joint work with Xi Chen of Tsinghua University.
Speaker Details
Dr. Shang-Hua Teng is currently a full professor in the Computer Science Department at Boston University. He taught as a faculty member in the Department of Mathematics of MIT and in the Computer Science Departments of the University of Minnesota and UIUC.He has worked and consulted for Akamai Technologies, IBM Almaden Research Center, Intel Corporation, Xerox PARC, Cray Research/SGI, Thinking Machine Corporation, and NASA Ames Research Center. He is an Alfred P. Sloan Fellow, winner of the Senior Xerox Award for Outstanding Faculty Research (UIUC), and has received the NSF Faculty Early Career Development Award.Dr. Teng received a B.S. degree in computer science and a B.A. degree in electrical engineering from Shanghai Jiao Tong University in 1985, an M.S. degree in computer science from University of Southern California (USC) in 1988, and a Ph.D. degree in computer science from Carnegie Mellon University (CMU) in 1991.With Dan Spielman of MIT, he developed the theory of Smoothed Analysis for modeling and analyzing practical algorithms, and had demonstrated that the simplex method for linear programming has a polynomial smoothed complexity. This joint work was cited by National Science Foundation in its FY’03 budget request to Congress. His research centers on the design and analysis of efficient algorithms. His recent interests include computational game theory, spectral graph theory and its applications in optimization and information processing, parallel scientific computing, computational geometry, graph partitioning and clustering, and cryptography. He has also received 8 US Patents for his work on compiler optimization and Internet technology.
- Date:
- Speakers:
- Shang-Hua Teng
-
-
Jeff Running
-
