February 1 – 6 , 2004, Dagstuhl Seminar 04061

Real Computation and Complexity


Thomas Lickteig (University of Limoges, FR)
Klaus Meer (University of Southern Denmark – Odense, DK)
Luis Miguel Pardo (University of Cantabria, ES)

For support, please contact

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
List of Participants
Dagstuhl's Impact: Documents available


The seminar "Real Computation and Complexity" was intended as a meeting place of several tendencies in the complexity analysis of algorithms in real computation. One main idea therefore was to bring together scientists with rather different backgrounds such as numerical analysis, symbolic computing, real and complex algebraic geometry, logic, differential algebra and computational complexity. This broadness guaranteed to get a thorough overview of current results, methods and trends in the area. It allowed as well to discuss main problems related to all aspects of real computation and complexity from different perspectives.

The seminar was attended by 43 participants from 14 different countries (Argentina, Belgium, Brazil, Canada, Denmark, Germany, England, France, Israel, Italy, Russia, Spain, Switzerland, USA). During the five days 34 talks were presented.

The main topics of the seminar as addressed either in talks or in informal discussions were the following:

  • complexity upper bounds for linear optimization problems;
  • models of computation with real numbers and structural transfer results between them;
  • complexity issues and algorithmics in symbolic and numeric multivariate polynomial equation solving and elimination theory;
  • quantitative aspects in real equation solving;
  • algorithmic aspects and quantitative estimates in differential equation solving;
  • fast evaluation of polynomial and analytic functions.

The Dagstuhl-Seminar was devoted to honor renowned scientist, complexity theory pioneer and celebrity Arnold Schönhage on the occasion of his 70th birthday in December 2004. There will be a Festschrift for Arnold Schönhage special volume of Journal of Complexity issue of this Dagstuhl seminar.

Dagstuhl Seminar Series


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.