Title:  Matching Algorithmic Bound for Finding a Brouwer Fixed Point
Speaker: Chen Xi
Tsinghua University


Date: Friday, March 18, 2005
Time 11-12
Venue: Room 3464, HKUST


Abstract
We study the algorithmic complexity of the discrete fixed point problem and
develop an asymptotic matching bound
for a cube in any constantly bounded finite dimension. To obtain our upper
bound, we derive a new fixed point
theorem, based on a novel characterization of boundary conditions for the
existence of fixed points.

In addition, exploring a linkage with the approximation problem of the
continuous fixed point problem, we obtain
asymptotic matching bounds for complexity of the approximate Brouwer fixed
point problem in the continuous case
for Lipschitz functions that close a previous exponential gap.  It settles a
fifteen years old open problem of
Hirsch, Papadimitriou and Vavasis by improving both the upper and lower
bounds.

Our new characterization for existence of a fixed point is also applicable
to functions defined on non-convex
domain and makes it a potentially useful tool for design and analysis of
algorithms for fixed points in general
domain.