Title:	Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation
Date:	January 29, 2007 (Monday)
Time:	2:30 p.m. - 3:30 p.m.
Venue:	Room 121, 1/F, Ho Sin-hang Engineering Building, The Chinese University of Hong Kong, Shatin, N.T.
Speaker:	Mr. Xi Chen PhD student Department of Computer Science Tsinghua University China

ABSTRACT:

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 (n^{d/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 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 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 (n^{d-1})$.

This is a joint work with Shang-Hua Teng.

BIOGRAPHY:

I am a fourth-year PhD student in the department of Computer Science at Tsinghua University. I studied in the Physics department of Tsinghua University and received my B.S. there in 2003.

My research interests lie in the area of Theoretical Computer Science. I am particularly interested in the computational complexity of natural problems in Algorithmic Game Theory and Computational Biology.

Enquiries: Miss Temmy So at tel 2609 8444

For more information, please refer to http://www.cse.cuhk.edu.hk/seminar