TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 15391

Algorithms and Complexity for Continuous Problems

( Sep 20 – Sep 25, 2015 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/15391

Organizers

Contact


Impacts

Schedule

Motivation

The goal of the seminar is to bring together researchers from different communities working on computational aspects of continuous problems.

Continuous computational problems arise in diverse areas of science and engineering. Examples include path and multivariate integration, partial differential equations, approximation, optimization, as well as operator equations. Understanding the complexity of such problems and construction of efficient algorithms is both important and challenging.

Among the topics to be included are:

Compressed Sensing
Compressed sensing is a rapidly developing modern mathematical technology. It allows effective reconstruction of sparse or almost sparse signals from a few samples, much less than the Shannon rate requires for the reconstruction of arbitrary signals. First real world applications have been developed or are on the horizon. These include MRI, radar and sparse signal approximation in image processing.

Learning Theory
During the last decade, the field of learning theory has witnessed an enormous advance and growth. This progress was both triggered and made possible by successfully merging two quite different communities, namely the machine learning community, which traditionally resides in computer science, on the one hand and the mathematically oriented community of non-parametric statistics on the other hand.

Partial Differential Equations with Random Coefficients
Partial differential equations with random coefficients present many challenges. The dimensionality of the problem can be high or even infinite, and if the spatial variation of the field is rapid the quality of a finite-dimensional approximation will be poor, unless a very high dimensional approximation is allowed.

Multilevel Algorithms
The stochastic multi-level technique was invented about 15 years ago by Stefan Heinrich as a part of his theoretical work on the complexity of local and global solutions of integral equations. We are expecting further substantial progress on multi-level algorithms, both with respect to theory and to applications in more diverse areas.

Computational Stochastic Processes
We focus on quadrature problems for stochastic processes, which are given by ordinary and partial stochastic differential equations. While the majority of results in this area deals with globally Lipschitz coefficients and smooth integrands, such assumptions are typically not met for real world applications from biology, chemistry or computational finance.

Tractability of Multivariate Problems
This is a topic included in previous Dagstuhl Seminars. Many new questions will be discussed.

There will be another Seminar during the same week, 15392 "Measuring the Complexity of Computational Content: Weirauch Reducibility and Reverse Analysis" See www.dagstuhl.de/15392 for their Motivation text.


Summary

This was already the 12th Dagstuhl Seminar on Algorithms and Complexity for Continuous Problems over a period of 24 years. It brought together researchers from different communities working on computational aspects of continuous problems, including computer scientists, numerical analysts, applied and pure mathematicians. Although the seminar title has remained the same, many of the topics and participants change with each seminar and each seminar in this series is of a very interdisciplinary nature.

Continuous computational problems arise in diverse areas of science and engineering. Examples include path and multivariate integration, approximation, optimization, as well as operator equations. Typically, only partial and/or noisy information is available, and the aim is to solve the problem within a given error tolerance using the minimal amount of computational resources. For example, in high-dimensional integration one wants to compute an epsilon-approximation to the integral with the minimal number of function evaluations. Here it is crucial to identify first the relevant variables of the function. Understanding the complexity of such problems and construction of efficient algorithms is both important and challenging. The current seminar attracted 35 participants from nine different countries all over the world. About 30% of them were young researchers including PhD students. There were 25 presentations covering in particular the following topics:

  • High-dimensional problems
  • Tractability
  • Computational stochastic processes
  • Compressive sensing
  • Random media
  • Computational finance
  • Noisy data
  • Learning theory
  • Biomedical learning problems
  • Markov chains

There were three introductory talks to recent developments in PDE with random coefficients, learning theory and compressive sensing. A joint session with the Dagstuhl Seminar 15392 "Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis" stimulated the transfer of ideas between the two different groups present in Dagstuhl.

The work of the attendants was supported by a variety of funding agencies. This includes the Deutsche Forschungsgemeinschaft, the Austrian Science Fund, the National Science Foundation (USA), and the Australian Research Council.

As always, the excellent working conditions and friendly atmosphere provided by the Dagstuhl team have led to a rich exchange of ideas as well as a number of new collaborations. Selected papers related to this seminar will be published in a special issue of the Journal of Complexity.

Copyright Aicke Hinrichs, Joseph F. Traub, Henryk Wozniakowski, and Larisa Yaroslavtseva

Participants
  • James M. Calvin (NJIT - Newark, US) [dblp]
  • Ronald Cools (KU Leuven, BE) [dblp]
  • Sonja Cox (University of Amsterdam, NL) [dblp]
  • Steffen Dereich (Universität Münster, DE) [dblp]
  • Stefan Geiss (University of Jyväskylä, FI) [dblp]
  • Michael Gnewuch (Universität Kiel, DE) [dblp]
  • Mario Hefter (TU Kaiserslautern, DE) [dblp]
  • Stefan Heinrich (TU Kaiserslautern, DE) [dblp]
  • Aicke Hinrichs (Universität Linz, AT) [dblp]
  • Alexander Keller (NVIDIA GmbH - Berlin, DE) [dblp]
  • Peter Kritzer (Universität Linz, AT) [dblp]
  • Thomas Kühn (Universität Leipzig, DE) [dblp]
  • Peter Mathé (Weierstraß Institut - Berlin, DE) [dblp]
  • Thomas Müller-Gronbach (Universität Passau, DE) [dblp]
  • Andreas Neuenkirch (Universität Mannheim, DE) [dblp]
  • Dong Nguyen (KU Leuven, BE) [dblp]
  • Erich Novak (Universität Jena, DE) [dblp]
  • Dirk Nuyens (KU Leuven, BE) [dblp]
  • Jens Oettershagen (Universität Bonn, DE)
  • Sergei Pereverzyev (RICAM - Linz, AT) [dblp]
  • Leszek Plaskota (University of Warsaw, PL) [dblp]
  • Pawel Przybylowicz (AGH Univ. of Science & Technology-Krakow, PL) [dblp]
  • Holger Rauhut (RWTH Aachen, DE) [dblp]
  • Klaus Ritter (TU Kaiserslautern, DE) [dblp]
  • Daniel Rudolf (Universität Jena, DE) [dblp]
  • Winfried Sickel (Universität Jena, DE) [dblp]
  • Pawel Siedlecki (University of Warsaw, PL) [dblp]
  • Ian H. Sloan (UNSW - Sydney, AU) [dblp]
  • Jeremy Staum (Northwestern University - Evanston, US) [dblp]
  • Ingo Steinwart (Universität Stuttgart, DE) [dblp]
  • Mario Ullrich (Universität Linz, AT) [dblp]
  • Tino Ullrich (Universität Bonn, DE) [dblp]
  • Markus Weimar (Universität Marburg, DE) [dblp]
  • Larisa Yaroslavtseva (Universität Passau, DE) [dblp]
  • Marguerite Zani (Université d'Orléans, FR) [dblp]

Related Seminars
  • Dagstuhl Seminar 9116: Algorithms and Complexity of Continuous Problems (1991-04-15 - 1991-04-19) (Details)
  • Dagstuhl Seminar 9242: Algorithms and Complexity for Continuous Problems (1992-10-12 - 1992-10-16) (Details)
  • Dagstuhl Seminar 9442: Algorithms and Complexity for Continuous Problems (1994-10-17 - 1994-10-21) (Details)
  • Dagstuhl Seminar 9643: Algorithms and Complexity for Continuous Problems (1996-10-21 - 1996-10-25) (Details)
  • Dagstuhl Seminar 98201: Algorithms and Complexity for Continuous Problems (1998-05-18 - 1998-05-22) (Details)
  • Dagstuhl Seminar 00391: Algorithms and Complexity for Continuous Problems (2000-09-24 - 2000-09-29) (Details)
  • Dagstuhl Seminar 02401: Algorithms and Complexity for Continuous Problems (2002-09-29 - 2002-10-04) (Details)
  • Dagstuhl Seminar 04401: Algorithms and Complexity for Continuous Problems (2004-09-26 - 2004-10-01) (Details)
  • Dagstuhl Seminar 06391: Algorithms and Complexity for Continuous Problems (2006-09-24 - 2006-09-29) (Details)
  • Dagstuhl Seminar 09391: Algorithms and Complexity for Continuous Problems (2009-09-20 - 2009-09-25) (Details)
  • Dagstuhl Seminar 12391: Algorithms and Complexity for Continuous Problems (2012-09-23 - 2012-09-28) (Details)
  • Dagstuhl Seminar 19341: Algorithms and Complexity for Continuous Problems (2019-08-18 - 2019-08-23) (Details)
  • Dagstuhl Seminar 23351: Algorithms and Complexity for Continuous Problems (2023-08-27 - 2023-09-01) (Details)

Classification
  • data structures / algorithms / complexity

Keywords
  • Compressed sensing
  • Learning theory
  • Random coefficients
  • Multilevel algorithms
  • Computational stochastic processes
  • Tractability