24. – 29. September 2006, Dagstuhl Seminar 06391

Algorithms and Complexity for Continuous Problems


Stephan Dahlke (Universität Marburg, DE)
Klaus Ritter (TU Darmstadt, DE)
Ian H. Sloan (UNSW – Sydney, AU)
Joseph F. Traub (Columbia University – New York, US)

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team


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


The seminar was devoted to the branch of computational complexity that studies continuous problems for which only partial information is available. As an important example we mention an operator equation L x = y: here the right-hand side y and the coefficients of the (differential or integral) operator L are functions on some domain. These functions may only be evaluated at a finite number of properly chosen knots for the approximate computation of the solution x. Any such information about the coefficients is partial in the sense that it typically does not determine the solution x exactly.

The 8th Dagstuhl Seminar on Algorithms and Complexity of Continuous Problems attracted 50 participants from Computer Science and Mathematics, representing 11 countries and 4 continents. Among them have been 19 young researchers, some of whom have just received there diploma or master degree.

There were 43 presentations covering in particular the following topics:

  1. complexity and tractability of high-dimensional problems,
  2. complexity of operator equations and non-linear approximation,
  3. quantum computation,
  4. stochastic computation and quantization
  5. complexity of stochastic computation and quantization, and
  6. complexity and regularization of ill-posed problems,

together with applications in financial engineering and computer graphics. Abstracts are included in these Seminar Proceedings.

In addition to the substantial number of young participants another key feature of the seminar was the interaction between scientists working in different areas, namely, numerical analysis and scientific computing, probability theory and statistics, number theory, and theoretical computer science. In particular, distinguished researchers from numerical analysis were invited, and the mutual exchange of ideas was very inspiring and created many new ideas. Especially, one of the most challenging features of modern numerical analysis is the treatment of high-dimensional problems which requires several new paradigma. It has turned out that many developments that have been achieved in the IBC-community such as high-dimensional quadrature etc. will probably play a central role in this context, so that merging together the different approaches and ideas will be a very exciting topic in the near future.

Moreover, the meeting helped us to create new and to maintain the already existing various collaborations. Some ideas devoloped at the meeting have already flown into joint applications for reseach grants.

The organizers would like to thank all the attendees for their participation, and the Dagstuhl team for the excellent working environment and the hospitality at the Schloss.

Dagstuhl Seminar Series


  • Continuous Algorithms/complexity


  • Continuous algorithms
  • Continuous complexity
  • Tractability
  • High-dimensional problems
  • Operator equations
  • Quantum computation
  • Stochastic computation
  • Ill-posed problems
  • Monte Carlo
  • Qubit complexity
  • Random noise
  • Approximation theory
  • Lattice rules


Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).


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.