Algorithms and Complexity for Continuous Problems

Summary

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.