Algorithms and Complexity for Continuous Problems

Summary

The Dagstuhl-Seminar on Algorithms and Complexity of Continuous Problems was attended by 39 computer scientists and mathematicians from 12 countries. We express our gratitude to the staff of Schloß Dagstuhl for providing a great atmosphere. Our Seminar was devoted to the study of continuous problems such as computation over the reals, decision problems, problems with noisy data, numerical integration, optimal recovery, n-widths, partial differential equations, integral equations, zero finding, linear programming and image reconstruction.

The Report contains problems on finite dimensional as well as on infinite dimensional spaces. In the finite dimensional case the information is usually complete and the computational cost is crucial. In the infinite dimensional case the information is usually partial and in most of the research done so far the information cost is crucial. The Seminar-Report contains the abstracts of 32 lectures in alphabetical order. We also had a plenary session on new research directions and open questions.