The field of algorithmic complexity of real computational problems has received much attention in recent years. This topic with geometrical, algebraic, analytic, and numerical aspects encompasses the foundational area of scientific computing and has a wide range of relevant applications. The main object is the computation with polynomials, the better understanding of what makes these computations difficult or easy in order to design faster Computer algebra algorithms. Due to their omnipresence, the case of real polynomials evidently plays a predominant role. Many new algorithms have been designed during the last decade for deciding the existence of solutions of equations and inequalities, or for computing solutions.

The seminar was intended to be broad and open. While clearly focussed on real computational problems, scientists with rather different backgrounds such as computer science, numerical analysis, algebraic geometry, logic, and abstract real algebraic geometry could be brought together to know and discuss main problems from different perspectives. This is important as scientific questions often don't find their answers within their domain of origin. One aim of the seminar was to support the collaboration of people of different origin.

We had 33 participants coming from Belgium, France, Germany, Great Britain, Italy, Poland, Russia, Spain, and the United States. During the meeting 30 lectures have been given that have been continued by informal evening discussions in smaller groups. The talks focussed on new concrete algorithmic results, others introduced to main ongoing work or to the way of looking at things in important neighbouring fields. Main topics addressed include

• quantitative bounds in real algebraic geometry related to lower and upper complexity bounds,
• computation schemes (straight line programs) as basic data structure to cope with multivariate polynomial computation,
• translation of theoretical knowledge into fast implementations, univariate and multivariate root finding and root isolation,
• BSS discussion of differential equations, other ground fields, and counting problems,
• exact real computation, and
• approximation methods in the bit model.

Both, senior researchers as well as young researchers contributed to seminar. A Journal of Complexity (http://www.apnet.com/www/journal/cm.htm) special issue is dedicated to the workshop with selected papers addressing topics covered by this seminar.

The field has two major challenges. The first one, on the theoretical level, is the mathematical understanding of obstructions to the existence of fast polynomial computations, that is to say, lower bounds via an intrinsic inherent geometric complexity of a computational task. By knowing what must be avoided knowledge of lower bounds can furnish a guide-line in the design of algorithms. The second one, the design, is just now going in the direction of putting into effective use the theoretical knowledge of algebraic and arithmetic complexity, that is to say, translation into really real real algorithms that are fast in practice with new basic organisational designs.

We thank the IBFI scientific board for making available to us the Schloss Dagstuhl conference centre. Likewise we express our sincere appreciation of the outstanding organisation of Dagstuhl. On behalf of all participants we thank Dagstuhl for making available support by the TMR program of the European Community funding the participation of young European researchers and keynote speakers.