##### Dagstuhl Seminar 19341

### Algorithms and Complexity for Continuous Problems

##### ( Aug 18 – Aug 23, 2019 )

##### Permalink

##### Organizers

- Dmitriy Bilyk (University of Minnesota - Minneapolis, US)
- Aicke Hinrichs (Johannes Kepler Universität Linz, AT)
- Frances Y. Kuo (UNSW Sydney, AU)
- Klaus Ritter (TU Kaiserslautern, DE)

##### Contact

- Michael Gerke (for scientific matters)
- Annette Beyer (for administrative matters)

##### Shared Documents

- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)

##### Schedule

The goal of this Dagstuhl Seminar is to bring together researchers from different communities working on complexity of continuous problems. Such problems, which originate from numerous areas, including physics, chemistry, finance, and economics, can almost never be solved analytically, but rather only approximately to within some error threshold. The complexity analysis ideally includes the construction of (asymptotically) optimal algorithms. The following topics will be covered:

**Tractability analysis of high-dimensional problems:** Tractability analysis is an area of applied mathematics and theoretical computer science that studies the minimal computational resources needed for the approximate solution of problems with a huge number of variables, and it can be seen as a unifying theme for the preceding seminars in this series. Many concrete problems from applications have been analyzed in this context, new algorithms were developed, approaches to break the curse of dimensionality were established, but there remain a number of important open problems. Tractability analysis will serve as a guideline and a tool for establishing complexity results and for constructing algorithms for infinite dimensional problems.

**Computational stochastics:** The focus will be on weak and strong approximation as well as on the quadrature problem for stochastic ordinary or partial differential equations, i.e., on models with a random dynamics in a finite- or infinite-dimensional state space. A major topic will be the complexity analysis for stochastic differential equations under non-standard assumptions.

**Computing and complexity in infinite dimensions:** Computational problems with infinitely many variables naturally arise in rather different application areas. Results and techniques from tractability analysis are available and thus permit one to study infinite dimensional problems as the limit of finite dimensional ones. Moreover, the availability of generic types of algorithms, like the multivariate decomposition method or the multi-level approach, will contribute to the complexity analysis and practical application in integration and approximation problems of infinitely many variables.

**Discrepancy theory:** Classical discrepancy theory is concerned with the question how uniformly finite point sets can be distributed. The geometric notion of discrepancy is intimately connected to the complexity of integration for functions from certain function classes. For problems in both fixed low dimension and high dimension, there are intriguing open questions whose solution would impact both fields of discrepancy theory and tractability studies.

**Computational/applied harmonic analysis:** Harmonic analysis plays an increasingly important role both in discrepancy theory and tractability analysis. One highlight is the proof of the currently best known lower bound for the star discrepancy in fixed dimension, which showed close connections between different areas, so similar techniques could be used to establish better bounds for the celebrated small ball problem for Gaussian processes. Equally important for the seminar is that many of the interesting spaces of functions occurring in numerical problems are well suited to the application of harmonic analysis.

As we understand better and better, these subjects are highly interrelated, and they are probably the most active and promising ones in the fields for the next decade. Bringing together a mix of junior and senior researchers from these diverse but interrelated subjects in this Dagstuhl Seminar, we expect considerable progress both for the theory and the applications in these areas.

This was already the 13th Dagstuhl Seminar on Algorithms and Complexity for Continuous Problems over a period of 28 years. It brought together researchers from different communities working on complexity of continuous problems. Such problems, which originate from numerous areas, including physics, chemistry, finance, and economics, can almost never be solved analytically, but rather only approximately to within some error threshold. The complexity analysis ideally includes the construction of (asymptotically) optimal algorithms. 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. The current seminar attracted 41 participants from nine different countries all over the world. About 30% of them were young researchers including PhD students. There were 34 presentations.

The following topics were covered:

**Tractability analysis of high-dimensional problems:** Tractability analysis is an area of applied mathematics and theoretical computer science that studies the minimal computational resources needed for the approximate solution of problems with a huge number of variables, and it can be seen as a unifying theme for the preceding seminars in this series. Many concrete problems from applications have been analyzed in this context, new algorithms were developed, approaches to break the curse of dimensionality were established, but there remain a number of important open problems. Tractability analysis will serve as a guideline and a tool for establishing complexity results and for constructing algorithms for infinite dimensional problems.

**Computational stochastics:** The focus was on weak and strong approximation as well as on the quadrature problem for stochastic ordinary or partial differential equations, i.e., on models with a random dynamics in a finite- or infinite-dimensional state space. A major topic was the complexity analysis for stochastic differential equations under non-standard assumptions.

**Computing and complexity in infinite dimensions:** Computational problems with infinitely many variables naturally arise in rather different application areas. Results and techniques from tractability analysis are available and thus permit one to study infinite dimensional problems as the limit of finite dimensional ones. Moreover, the availability of generic types of algorithms, like the multivariate decomposition method or the multi-level approach, will contribute to the complexity analysis and practical application in integration and approximation problems of infinitely many variables.

**Discrepancy theory:** Classical discrepancy theory is concerned with the question how uniformly finite point sets can be distributed. The geometric notion of discrepancy is intimately connected to the complexity of integration for functions from certain function classes. For problems in both fixed low dimension and high dimension, there are intriguing open questions whose solution would impact both fields of discrepancy theory and tractability studies.

**Computational/applied harmonic analysis:** Harmonic analysis plays an increasingly important role both in discrepancy theory and tractability analysis. One highlight is the proof of the currently best known lower bound for the star discrepancy in fixed dimension, which showed close connections between different areas, so similar techniques could be used to establish better bounds for the celebrated small ball problem for Gaussian processes. Equally important for the workshop is that many of the interesting spaces of functions occurring in numerical problems are well suited to the application of harmonic analysis.

As we understand better and better, these subjects are highly interrelated, and they are probably the most active and promising ones in the fields for the next decade. Bringing together a mix of junior and senior researchers from these diverse but interrelated subjects in a Dagstuhl seminar resulted in considerable progress both for the theory and the applications in these areas.

Seminars in applied mathematics and theoretical computer science typically consist of presentations, followed by short discussions in the plenum, and numerous informal discussions in smaller groups. In this seminar, we added another new feature. A moderator was assigned to three preselected talks (based on their particular relevance and on the experience of the speaker) in order to inspire a longer, in-depth discussion in the plenum. The three speakers were Jan Výbyral, Erich Novak, and Martin Hutzenthaler. The talks were scheduled as the first talks on Tuesday, Wednesday and Thursday. It was indeed very inspiring to witness the long and deep discussions following these special talks. We feel that this format was successful and should be used also in other workshops and conferences of the community.

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.

- Dmitriy Bilyk (University of Minnesota - Minneapolis, US) [dblp]
- 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]
- Benjamin Doerr (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Martin Ehler (Universität Wien, AT) [dblp]
- Michael Giles (University of Oxford, GB) [dblp]
- Michael Gnewuch (Universität Osnabrück, DE) [dblp]
- Takashi Goda (University of Tokyo, JP) [dblp]
- Mario Hefter (TU Kaiserslautern, DE) [dblp]
- Stefan Heinrich (TU Kaiserslautern, DE) [dblp]
- Aicke Hinrichs (Johannes Kepler Universität Linz, AT) [dblp]
- Martin Hutzenthaler (Universität Duisburg-Essen, DE) [dblp]
- Lutz Kämmerer (TU Chemnitz, DE) [dblp]
- Alexander Keller (NVIDIA, DE) [dblp]
- Kristin Kirchner (ETH Zürich, CH) [dblp]
- David Krieg (Johannes Kepler Universität Linz, AT) [dblp]
- Peter Kritzer (Österreichische Akadamie der Wissenschaften - Linz, AT) [dblp]
- Robert J. Kunsch (RWTH Aachen, DE) [dblp]
- Frances Y. Kuo (UNSW Sydney, AU) [dblp]
- Gunther Leobacher (Universität Graz, AT) [dblp]
- Thomas Müller-Gronbach (Universität Passau, DE) [dblp]
- Erich Novak (Universität Jena, DE) [dblp]
- Dirk Nuyens (KU Leuven, BE) [dblp]
- Friedrich Pillichshammer (Johannes Kepler Universität Linz, AT) [dblp]
- Leszek Plaskota (University of Warsaw, PL) [dblp]
- Joscha Prochno (Universität Graz, AT) [dblp]
- Pawel Przybylowicz (AGH Univ. of Science & Technology-Krakow, PL) [dblp]
- Klaus Ritter (TU Kaiserslautern, DE) [dblp]
- Daniel Rudolf (Universität Göttingen, DE) [dblp]
- Stefan Steinerberger (Yale University - New Haven, US) [dblp]
- Michaela Szölgyenyi (Alpen-Adria-Universität Klagenfurt, AT) [dblp]
- Aretha Teckentrup (University of Edinburgh, GB) [dblp]
- Vladimir N. Temlyakov (University of South Carolina - Columbia, US) [dblp]
- Mario Ullrich (Johannes Kepler Universität Linz, AT) [dblp]
- Jan Vybíral (Czech Technical University - Prague, CZ) [dblp]
- Marcin Wnuk (Universität Kiel, DE) [dblp]
- Henryk Wozniakowski (Columbia University - New York, US) [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 15391: Algorithms and Complexity for Continuous Problems (2015-09-20 - 2015-09-25) (Details)
- Dagstuhl Seminar 23351: Algorithms and Complexity for Continuous Problems (2023-08-27 - 2023-09-01) (Details)

##### Classification

- data structures / algorithms / complexity

##### Keywords

- tractability analysis
- computational stochastics
- computing and complexity in infinite dimensions
- discrepancy theory
- applied harmonic analysis