The goal of this Dagstuhl Seminar is to bring together researchers that work in various fields united by a common theme of complexity of continuous problems. In this context, complexity refers to the computational effort required to solve the problem approximately, up to a given error. For these, often high- or even infinite-dimensional, problems it is desirable to have theoretical bounds on the complexity as well as explicit constructions of (nearly) optimal algorithms. Their applications range over natural sciences, economics, statistics, engineering, computer science (including computer graphics, global optimization, and machine learning) and other areas of interest. The seminar covers the following highly interrelated topics:

Tractability analysis of high-dimensional problems: Tractability analysis has its roots in information-based complexity. It studies continuous problems, where the instances are typically d-variate functions. The focus is on how the problem complexity depends on the error tolerance and on d. Major topics will be the study of recent notions of tractability and of worst-case errors over non-convex and unbounded domains.

Computational stochastics: We focus on strong approximation and quadrature of stochastic differential equations (SDEs) with non-globally Lipschitz continuous coefficients. Systematic investigations on the numerical approximation of such SDEs have started in the last decade and are still in their infancy. Major topics will be complexity analysis and the potential of adaptive strategies.

Infinite-variate problems: algorithms and complexity: Many applications rely on models with countably many variables. The complexity analysis of the resulting continuous problems may be viewed as the limit of tractability analysis for d-variate functions, where d tends to infinity. For many problems sharp complexity bounds have been proved with the help of generic types of algorithms, as multilevel algorithms and multivariate decomposition methods, but mainly in the case where the spaces of input functions are weighted reproducing kernel Hilbert spaces (RKHSs) based on product weights or RKHSs of increasing smoothness. A major topic will be the analysis of more general function spaces as, e.g., general weighted RKHSs or reproducing kernel Banach spaces.

Well-distributed point configurations: discrepancy, quasi-Monte Carlo methods, dispersion: Many problems in approximation theory and complexity rely on the existence and construction of good (random or deterministic) point distributions with respect to discrepancy, integration errors, strength of cubature formulas, dispersion, or discrete energy. Numerous questions in this area are still open: in various regimes sharp bounds for discrepancy and dispersion still remain unknown and explicit efficient constructions are still lacking. Collective effort of experts in approximation, complexity, discrete mathematics, and probability may bring substantial progress in these problems.

Linear and standard information in approximation theory: A classical problem of approximation theory, learning theory and data analysis is the approximation of an unknown multivariate function from incomplete information. The information can be given by a limited number of function evaluations (standard information) or by evaluating a finite number of arbitrary linear functionals (linear information). Even in the simplest setting of approximation in a norm of a Hilbert space, the relation between using standard information and linear information was understood only recently and there is still a number of challenging open questions in this area

Creative Commons BY 4.0

Dmitriy Bilyk, Michael Gnewuch, Jan Vybíral, and Larisa Yaroslavtseva

• Dmitriy Bilyk (University of Minnesota - Minneapolis, US) [dblp]
• François Clément (Sorbonne University - Paris, FR)
• Ronald Cools (KU Leuven, BE) [dblp]
• Steffen Dereich (Universität Münster, DE) [dblp]
• Benjamin Doerr (Ecole Polytechnique - Palaiseau, FR) [dblp]
• Carola Doerr (Sorbonne University - Paris, FR) [dblp]
• Michael Giles (University of Oxford, GB) [dblp]
• Michael Gnewuch (Universität Osnabrück, DE) [dblp]
• Kumar Harsha (Universität Osnabrück, DE) [dblp]
• Stefan Heinrich (RPTU - Kaiserslautern, DE) [dblp]
• Alexander Keller (NVIDIA, DE) [dblp]
• David Krieg (Johannes Kepler Universität Linz, AT) [dblp]
• Peter Kritzer (Österreichische Akadamie der Wissenschaften - Linz, AT) [dblp]
• Thomas Kühn (Universität Leipzig, DE) [dblp]
• Robert J. Kunsch (RWTH Aachen, DE & TU Chemnitz, DE) [dblp]
• Frances Y. Kuo (UNSW Sydney, AU) [dblp]
• Laura Lippert (TU Chemnitz, DE)
• Alexander Litvak (University of Alberta - Edmonton, CA) [dblp]
• Michelle Mastrianni (University of Minnesota - Minneapolis, US) [dblp]
• Peter Mathé (Weierstraß Institut - Berlin, DE) [dblp]
• Weiwen Mo (KU Leuven, BE) [dblp]
• Thomas Müller-Gronbach (Universität Passau, DE) [dblp]
• Erich Novak (Friedrich-Schiller-Universität Jena, DE) [dblp]
• Dirk Nuyens (KU Leuven, BE) [dblp]
• Zexin Pan (Stanford University, US) [dblp]
• Kateryna Pozharska (National Academy of Sciences of Ukraine - Kiev, UA & TU Chemnitz, DE) [dblp]
• Pawel Przybylowicz (AGH Univ. of Science & Technology-Krakow, PL) [dblp]
• Klaus Ritter (RPTU - Kaiserslautern, DE) [dblp]
• Daniel Rudolf (Universität Passau, DE) [dblp]
• Robin Rüßmann (RPTU - Kaiserslautern, DE) [dblp]
• Mathias Sonnleitner (Universität Passau, DE) [dblp]
• Abirami Srikumar (UNSW Sydney, AU) [dblp]
• Stefan Steinerberger (University of Washington - Seattle, US) [dblp]
• Olivier Teytaud (Meta AI Research - Tournon-sur-Rhone, FR) [dblp]
• Mario Ullrich (Johannes Kepler Universität Linz, AT) [dblp]
• Tino Ullrich (TU Chemnitz, DE) [dblp]
• Jan Vybíral (Czech Technical University - Prague, CZ) [dblp]
• Christian Weiß (Hochschule Ruhr-West - Mülheim, DE)
• Laurence Wilkes (KU Leuven, BE) [dblp]
• Marcin Wnuk (Universität Osnabrück, DE) [dblp]