https://www.dagstuhl.de/19341

August 18 – 23 , 2019, Dagstuhl Seminar 19341

Algorithms and Complexity for Continuous Problems

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)

For support, please contact

Annette Beyer for administrative matters

Michael Gerke for scientific matters

Documents

List of Participants
Shared Documents
Dagstuhl Seminar Wiki
Dagstuhl Seminar Schedule (Upload here)

(Use seminar number and access code to log in)

Motivation

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.

License
  Creative Commons BY 3.0 DE
  Dmitiy Bilyk, Aicke Hinrichs, Frances Y. Kuo, and Klaus Ritter

Dagstuhl Seminar Series

Classification

  • Data Structures / Algorithms / Complexity

Keywords

  • Tractability analysis
  • Computational stochastics
  • Computing and complexity in infinite dimensions
  • Discrepancy theory
  • Applied harmonic analysis

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support