Maxwell Institute Colloquium 2011

Felipe Cucker, City University of Hong Kong

On Smale's 17th Problem

  • Colloquium Lecture May 13, 2011
  • James Clerk Maxwell Building Lecture Theatre C
  • Time 16:10

At the request of the International Mathematical Union, in 1999, Steve Smale proposed a list of 18 problems for the mathematicians of the 21st century. The 17th of these problems asks for the existence of a deterministic algorithm computing an approximate solution of a system of n complex polynomials in n unknowns in time polynomial, on the average, in the size N of the input system. The talk gives fundamental advances in this problem including the smoothed analysis of a randomized algorithm and a deterministic algorithm working in near-polynomial average time.

About the Speaker

Felipe Cucker is Chair Professor of Mathematics at the City University of Hong Kong. He has contributed ground-breaking research in a wide variety of fields such as computational complexity theory, foundations of optimization and numerical analysis, real algebraic geometry, learning theory, language evolution, dynamics of flocking, and probability theory. Among his books are Complexity and Real Computation (with Lenore Blum, Steve Smale, and Mike Shub), Mathematical Foundations of Learning, and an upcoming treatise on Mathematics and the Arts.

Professor Cucker is currently the chairman of the Society for the Foundations of Computational Mathematics and is a member of Barcelona's Royal Academy of Sciences and Arts.

Computational Complexity Challenges in Optimization

  • Symposium May 12, 2011
  • Informatics Forum Room 4.31
  • Time: 9:00-17:00

Speakers include:

  • Dennis Amelunxen, Paderborn
  • Michel Baes, ETH Zürich
  • Coralia Cartis, Edinburgh
  • Felipe Cucker, Hong Kong
  • Kousha Etessami, Edinburgh
  • Raphael Hauser, Oxford
  • Martin Lotz, Edinburgh
  • Javier Peña, Carnegie Mellon
  • Peter Richtárik, Edinburgh

Programme and Abstracts

Please refer to the full Programme Schedule [edit: schedule is no longer available].


There is no registration fee. If you would like to attend, please let the organizers Coralia Cartis (coralia.cartis at or Martin Lotz (martin.lotz at know of your intention; it would be helpful with catering provision.

Travel / Directions

The James Clerk Maxwell Building is located on the King's Buildings campus on Mayfield Road, while the Informatics Forum is located close to the city centre. Directions can be found at the Campus Maps website.


Please contact the organisers Coralia Cartis (coralia.cartis at or Martin Lotz (martin.lotz at for arrangements regarding accomodation.


Useful Resources