https://www.dagstuhl.de/06391

September 24 – 29 , 2006, Dagstuhl Seminar 06391

Algorithms and Complexity for Continuous Problems

Organizers

Stephan Dahlke (Universität Marburg, DE)
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

List of Participants
Dagstuhl's Impact: Documents available

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.

Dagstuhl Seminar Series

Classification

  • Continuous Algorithms/complexity

Keywords

  • Continuous algorithms
  • Continuous complexity
  • Tractability
  • High-dimensional problems
  • Operator equations
  • Quantum computation
  • Stochastic computation
  • Ill-posed problems
  • Monte Carlo
  • Qubit complexity
  • Random noise
  • Approximation theory
  • Lattice rules

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.