Editors’ preface

This volume is composed of six contributions derived from the lectures given

during the UIMP–RSME Llu´ ıs Santal´ o Summer School on “Recent Advances in

Real Complexity and Computation”. The goal of this Summer School was to present

some of the recent advances on Smale’s 17th Problem. This Problem was stated by

Steve Smale as follows:

Problem 1 (Smale’s 17th Problem). Can a zero of n complex polynomial equa-

tions in n unknowns be found approximately, on the average, in polynomial time

with a uniform algorithm?

These contributions cover several aspects around this problem: from numerical

to symbolic methods in polynomial equation solving, computational complexity as-

pects (both worse and average cases, both upper and lower complexity bounds) and

even aspects of the underlying geometry of the problem. Some of the contributions

also deal with either real or multiple solutions solving.

The School was oriented to graduate mathematicians, as to Master or Ph. D.

students in Mathematics and to senior researchers interested on this topic.

The School was promoted and supported by the Spanish Royal Mathematical

Society (RSME) and hosted by the Universidad Internacional Men´ endez Pelayo

(UIMP), from July 16th to July 20th of 2012, in El Palacio de la Magdalena, San-

tander. Partial financial support was also granted by the University of Cantabria

and the Spanish Ministry of Science Grant MTM2010-16051. We thank these in-

stitutions and grants for their financial support.

The speakers (in alphabetical order) and their courses in this Summer School

were the following ones:

• Carlos Beltr´ an,“Stability, precision and complexity in some numerical

problems”.

• Marc Giusti, “Polar, co–polar and bipolar varieties: real solving of alge-

braic varieties with intrinsic complexity”.

• Joos Heintz, “On the intrinsic complexity of elimination problems in ef-

fective algebraic geometry”.

• Gregorio Malajovich, “From the quadratic convergence of Newton’s method

to problems of counting of the number of solutions”.

• Klaus Meer,“Real Number Complexity Theory and Probabilistically Check-

able Proofs (PCPs)”.

• Michael Shub,“The geometry of condition and the analysis of algorithms”.

• Jean-Claude Yakoubsohn, “ Tracking multiplicities”.

ix