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 23351

Algorithms and Complexity for Continuous Problems

( Aug 27 – Sep 01, 2023 )

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

Organizers
  • Dmitriy Bilyk (University of Minnesota - Minneapolis, US)
  • Michael Gnewuch (Universität Osnabrück, DE)
  • Jan Vybíral (Czech Technical University - Prague, CZ)
  • Larisa Yaroslavtseva (Universität Graz, AT)

Contact

Motivation

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

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

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)

Classification
  • Computational Complexity
  • Data Structures and Algorithms
  • Numerical Analysis

Keywords
  • Tractability Analysis
  • Computational Stochastics
  • Infinite-Variate Problems
  • Quasi-Monte Carlo Methods
  • Sampling