##### Dagstuhl Seminar 15391

### Algorithms and Complexity for Continuous Problems

##### ( Sep 20 – Sep 25, 2015 )

##### Permalink

##### Organizers

- Aicke Hinrichs (Universität Linz, AT)
- Joseph F. Traub (New York, US)
- Henryk Wozniakowski (Columbia University - New York, US)
- Larisa Yaroslavtseva (Universität Passau, DE)

##### Contact

- Andreas Dolzmann (for scientific matters)
- Annette Beyer (for administrative matters)

##### Impacts

- A linear functional strategy for regularized ranking : article pp. 26-35 - Kriukova, Galina; Panasiuk, Oleksandra; Pereverzyev, Sergei V.; Tkachenko, Pavlo - Amsterdam : Elsevier, 2016 - (Neural Networks : 73. 2016).
- Complexity of linear ill-posed problems in Hilbert space - Mathe, Peter; Pereverzyev, Sergei V. - Linz : Johann Radon Institute, 2016. - 23 pp. - (RICAM-Report ; 2016-09).
- Embeddings of weighted Hilbert spaces and applications to multivariate and infinite-dimensional integration . article : pp. 8-39 - Gnewuch, Michael; Hefter, Mario; Hinrichs, Aicke; Ritter, Klaus - Amsterdam : Elsevier, 2017 - (Journal of Approximation Theory ; 222. 2017).
- Embeddings of Weighted Hilbert Spaces and Applications to Multivariate and Infinite-Dimensional Integration : article - Gnewuch, Michael; Hefter, Mario; Hinrichs, Aicke; Ritter, Klaus - ArXiv, 2016. - 35 pp..
- Glycemic Control Indices and Their Aggregation in the Prediction of Nocturnal Hypoglycemia From Intermittent Blood Glucose Measurements : article : pp. 1245-1250 - Sampath, Sivananthan; Tkachenko, Pavlo; Renard, Eric; Pereverzev, Sergei V. - (Journal of Diabetes Science and Technology ; 10. 2016, 6) - (Journal of Diabetes Science and Technology ; 10. 2016, 6 : article).
- Prediction of nocturnal hypoglycemia by an aggregation of previously known prediction approaches : proof of concept for clinical application : article : pp. 179-186 - Tkachenko, Pavlo; Kriukova, Galina; Aleksandrova, Marharyta; Chertov, Oleg; Renard, Eric; Pereverzyev, Sergei V. - Amsterdam : Elsevier, 2016 - (Computer Methods and Programs in Biomedicine ; 134. 2016).

##### Schedule

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.

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.

- 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