20. – 25. September 2015, Dagstuhl-Seminar 15391

Algorithms and Complexity for Continuous Problems


Aicke Hinrichs (Universität Linz, AT)
Joseph F. Traub (New York, US)
Henryk Wozniakowski (Columbia University – New York, US)
Larisa Yaroslavtseva (Universität Passau, DE)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Report, Volume 5, Issue 9 Dagstuhl Report
Dagstuhl's Impact: Dokumente verfügbar
Programm des Dagstuhl-Seminars [pdf]


This was already the 12th Dagstuhl Seminar on Algorithms and Complexity for Continuous Problems over a period of 24 years. It brought together researchers from different communities working on computational aspects of continuous problems, including computer scientists, numerical analysts, applied and pure mathematicians. 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.

Continuous computational problems arise in diverse areas of science and engineering. Examples include path and multivariate integration, approximation, optimization, as well as operator equations. Typically, only partial and/or noisy information is available, and the aim is to solve the problem within a given error tolerance using the minimal amount of computational resources. For example, in high-dimensional integration one wants to compute an epsilon-approximation to the integral with the minimal number of function evaluations. Here it is crucial to identify first the relevant variables of the function. Understanding the complexity of such problems and construction of efficient algorithms is both important and challenging. The current seminar attracted 35 participants from nine different countries all over the world. About 30% of them were young researchers including PhD students. There were 25 presentations covering in particular the following topics:

  • High-dimensional problems
  • Tractability
  • Computational stochastic processes
  • Compressive sensing
  • Random media
  • Computational finance
  • Noisy data
  • Learning theory
  • Biomedical learning problems
  • Markov chains

There were three introductory talks to recent developments in PDE with random coefficients, learning theory and compressive sensing. A joint session with the Dagstuhl Seminar 15392 "Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis" stimulated the transfer of ideas between the two different groups present in Dagstuhl.

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.

Summary text license
  Creative Commons BY 3.0 Unported license
  Aicke Hinrichs, Joseph F. Traub, Henryk Wozniakowski, and Larisa Yaroslavtseva

Dagstuhl-Seminar Series


  • Data Structures / Algorithms / Complexity


  • Compressed sensing
  • Learning theory
  • Random coefficients
  • Multilevel algorithms
  • Computational stochastic processes
  • Tractability


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.