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

## 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

- 19341: "Algorithms and Complexity for Continuous Problems" (2019)
- 15391: "Algorithms and Complexity for Continuous Problems" (2015)
- 12391: "Algorithms and Complexity for Continuous Problems" (2012)
- 09391: "Algorithms and Complexity for Continuous Problems" (2009)
- 06391: "Algorithms and Complexity for Continuous Problems " (2006)
- 04401: "Algorithms and Complexity for Continuous Problems" (2004)
- 00391: "Algorithms and Complexity for Continuous Problems" (2000)
- 98201: "Algorithms and Complexity for Continuous Problems" (1998)
- 9643: "Algorithms and Complexity for Continuous Problems" (1996)
- 9442: "Algorithms and Complexity for Continuous Problems" (1994)
- 9242: "Algorithms and Complexity for Continuous Problems" (1992)
- 9116: "Algorithms and Complexity of Continuous Problems" (1991)