Dagstuhl Seminar 27341
Algorithms and Complexity for Continuous Problems
( Aug 22 – Aug 27, 2027 )
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/27341
Organizers
- Dmitriy Bilyk (University of Minnesota - Minneapolis, US)
- David Krieg (Universität Passau, DE)
- Michaela Szölgyenyi (Alpen-Adria-Universität Klagenfurt, AT)
- Jan Vybíral (Czech Technical University - Prague, CZ)
Contact
- Andreas Dolzmann (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
The aim of this Dagstuhl Seminar is to promote discussions among researchers from different fields of mathematics and computer science who study the complexity of continuous problems. In this context, complexity refers to the computational effort required to solve the problem approximately, up to a given precision. In the analysis of high-dimensional (or even infinite dimensional) problems we are interested in both upper and lower bounds of their complexity. The most important areas covered by the seminar will include
Tractability and Information-Based Complexity: The area of Information-Based Complexity studies how much input information is necessary in order to be able to solve or approximate the solution of a given problem up to a desired precision. The objects of interest are typically high-dimensional functions and the complexity usually grows with the dimension. Tractability analysis investigates the dependence of the information complexity on the dimension and on the desired precision.
Algorithms and Complexity for Stochastic Differential Equations: We focus on strong and weak approximation of stochastic ordinary and partial differential equations with irregular coefficients which do not satisfy the global Lipschitz condition. We shall discuss for example the benefits of implicit or adaptive schemes as well as theoretical properties of the stochastic gradient method in machine learning. Identifying Tractable Models in High or Infinite-Dimensional Problems: It is well-known that many multivariate continuous problems suffer the curse of dimensionality and that they are intractable when the underlying dimension grows to infinity. On the other hand, there are interesting examples, where a small change in the setting can heavily influence this behavior and the problems become computationally feasible. These concepts include weighted spaces of functions of infinitely many variables, spaces of increasing smoothness, as well as the use of multivariate decomposition methods or reproducing kernel Banach spaces. We aim to discuss practically relevant settings of this phenomena, which could – for example – help to shed a new light on the remarkable success of artificial neural networks in real-life applications.
Well-distributed Point Configurations: Discrepancy, Quasi-Monte Carlo Methods, Dispersion: Well-distributed sets of points form a core of many applications in numerical analysis and computer science. The quality of the distribution can be measured in several ways and we focus on the so-called discrepancy and the dispersion of a point set. Surprisingly, tools from many mathematical disciplines (such as harmonic analysis, potential theory, randomized algorithms, discrete mathematics, algebra, or number theory) were used to provide constructions of well-distributed point clouds or to establish lower bounds. We plan to discuss new results and interactions of this area with new fields like extremal combinatorics, data compression, and training of neural networks.
Universal Algorithms: The tractability of multivariate problems is nowadays well understood for many instances of common problems. Unfortunately, in practical applications the assumptions of these models are usually not met, or at least hard to verify. On the other hand, we observed recently that quite simple concepts and algorithms (like least-squares methods, random information, l1-minimization, or the median method) achieve very often very good performance in a number of different problems. We want to discuss if these observations could be turned into a more systematic study of universality of algorithms.
Creative Commons BY 4.0
Dmitriy Bilyk, David Krieg, Michaela Szölgyenyi, and Jan Vybíral
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 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
- Information Theory
- Numerical Analysis
Keywords
- Complexity Theory
- Algorithms
- Numerics of Stochastic Differential Equations
- Numerical Analysis
