01. – 06. Februar 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)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
Dagstuhl's Impact: Dokumente verfügbar


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.

For a more detailed summary of the topics presented see the extended version of this report.
Summary only: pdf - ps

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 der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.