Complexity issues lie at the core of the theory of computation. The size of many practical problems demands the study of their intrinsic complexity and the efficiency of any proposed algorithms. Theoretical results have often resulted in real practical improvements in computation, such as that of Khachiyan who showed the polynomial-time solvability of linear programming in 1979 -- although the resulting "ellipsoid algorithm" was not practically competitive with the simplex method, it nevertheless led to modern interior-point algorithms which can outperform simplex algorithm on many large linear programs.

This workshop will involve three major subareas of complexity:

• Complexity of Algebraic Geometry-- the complexity of solving polynomial systems.
• Emerging themes in optimization--the above-mentioned ellipsoid algorithm shows the importance of fundamental results for practical applications.
• Algebraic and semi-algebraic Complexity--this area provides a uniform foundation for the first two.

There will be 5 short courses of 3 or 2 lectures each in these major areas, and a dozen talks of 45 minutes plus questions. We expect to leave enough free time to the participants to favour interaction and discussions.

We will also take the opportunity to celebrate Jean Pierre Dedieu's 60th birthday during a conference dinner in his honor, which will be preceded by a talk describing his major contributions to the field. 

Invited Speakers