Algorithms and Complexity for Continuous Problems

Summary

The goal of this workshop was to bring together researchers from different communities working on computational aspects of continuous problems.

Continuous computational problems arise in many areas of science and engineering. Examples include path and multivariate integration, function approximation, optimization, as well as differential, integral, and operator equations.

Understanding the complexity of such problems and constructing efficient algorithms is both important and challenging.

The workshop was of a very interdisciplinary nature with invitees from, e.g., computer science, numerical analysis, discrete, applied, and pure mathematics, physics, statistics, and scientific computation. Many of the lectures were presented by Ph.D. students.

Compared to earlier meetings, several very active research areas received more emphasis. These include quantum computing, complexity and tractability of high-dimensional problems, stochastic computation, and quantization, which was an entirely new field for this workshop.

Due to strong connections between the topics treated at this workshop many of the participants initiated new cooperations and research projects. The meeting was the eighth in a series of Dagstuhl-seminars on "Algorithms and Complexity for Continuous Problems". This topic belongs to the focus group research areas of the Working Group 1.1 of the International Federation for Information Processing. The work of the attendants was supported by a variety of funding agencies including the Deutsche Forschungsgemienschaft, the National Science Foundation and the Defense Advanced Research Projects Agency (USA), the Australian Research Council, and the State Committee for Research (Poland).

Selected papers from the workshop will be published in a special issue of the Journal of Complexity.

The following topics were discussed:

1. Complexity and Regularization of Ill-Posed Problems
2. Non-Linear Approximation
3. Tractability of High-Dimensional Numerical Problems
4. Quasi-Monte Carlo Methods
5. Quantum Computing
6. Stochastic: Computation and Quantization
7. Global Optimization
8. Differential and Integral Equation