https://www.dagstuhl.de/02401

September 29 – October 4 , 2002, Dagstuhl Seminar 02401

Algorithms and Complexity for Continuous Problems

Organizers

Leszek Plaskota (University of Warsaw, PL)
Klaus Ritter (TU Darmstadt, DE)
Ian H. Sloan (UNSW – Sydney, AU)
Joseph F. Traub (Columbia University – New York, US)

For support, please contact

Dagstuhl Service Team

Documents

Aims & Scope
List of Participants
Dagstuhl's Impact: Documents available
Dagstuhl-Seminar-Report 356

Summary

The seminar was devoted to the computational solution of continuous problems. Concrete algorithms and their analysis were discussed as well as complexity results were presented. Important continuous problems arise in different areas, and different techniques for analysis of these problems are necessary. Therefore the seminar attracted researchers from computer science, mathematics and applied mathematics, and statistics. There were altogether 46 participants representing 13 countries, among them 20 from Germany and 8 from the US. Together with senior and well recognized scientists, young prospective colleagues, some of them having just finished their diploma or master thesis, were also invited and presented their results.

A substantial part of the talks were devoted to numerical integration, with emphasis on problems with a large number of variables, and the algorithms under investigation were mainly Monte Carlo or quasi Monte Carlo methods. In some of these talks the computer-based construction of good deterministic cubature formulas was addressed.

A number of talks dealt with non-linear or operator equations, the latter being sometimes analyzed in a statistical setting with noisy data. Probabilistic concepts also played a role as a tool for analysis, e.g., for a problem from computational geometry or for global optimization, or as a part of the problem formulation itself, e.g., for solving stochastic differential equations.

Recently a new quantum model of computation has been introduced. Since quantum computers are potentially much more powerful than the classical ones, the quantum model is attracting great attention. At the Dagstuhl seminar 00931 in 2000 the first result concerning quantum algorithms for continuous problems was presented. Thereafter the quantum model has been included into several research projects related to the topics of the seminar. The current question is for what continuous problems the quantum model of computation offers an essential speed-up in solving them. There were 6 talks in which results on quantum complexity of summation, function approximation and integration were presented.

A selection of results presented at this conference will be published as invited papers in the Journal of Complexity.

The IBFI invited participants to a ceremony during our seminar, since Joe Traub, one of the seminar’s organizers, had his 70th birthday in 2002. We are grateful for this exceptional event, as well as for excellent working environment, the support, and the hospitality at Schloss Dagstuhl.

Dagstuhl Seminar Series

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.