Maxwell Institute Colloquium 2011

Maxwell Institute Colloquium
Felipe Cucker
City University of Hong Kong

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

On Smale's 17th Problem

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.

Prof. 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.

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

Computational Complexity Challenges in Optimization

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 see Schedule.

Registration

There is no registration fee. If you would like to attend, please let the organizers Coralia Cartis (coralia.cartis at ed.ac.uk) or Martin Lotz (martin.lotz at ed.ac.uk) 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.

Accomodation

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