Real Computation and Complexity

Summary

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.