http://www.dagstuhl.de/17481

26. November – 01. Dezember 2017, Dagstuhl Seminar 17481

Reliable Computation and Complexity on the Reals

Organisatoren

Norbert T. Müller (Universität Trier, DE)
Siegfried M. Rump (TU Hamburg-Harburg, DE)
Klaus Weihrauch (FernUniversität in Hagen, DE)
Martin Ziegler (KAIST – Daejeon, KR)

Auskunft zu diesem Dagstuhl Seminar erteilen

Simone Schilke zu administrativen Fragen

Andreas Dolzmann zu wissenschaftlichen Fragen

Dokumente

Teilnehmerliste
Gemeinsame Dokumente
Dagstuhl Seminar Wiki
Programm des Dagstuhl Seminars (Hochladen)

(Zum Einloggen bitte Seminarnummer und Zugangscode verwenden)

Motivation

The intention of this Dagstuhl Seminar is to bring together two groups of researchers working in related areas with quite orthogonal research directions: Reliable Computation and Complexity on the Reals.

Both communities are invited to exchange mutual views, challenges, and state of the art. The goal of the seminar is to unleash their full joint creativity via synergy: to foster interaction, to bridge, and to cross-promote; to tutor next generation scientists on the interface between both fields. They share, in addition to both building and being based on computer science, a solid background in mathematics and particularly advanced/hard real analysis. Moreover they have in common the emphasis on rigorous calculations with guaranteed error bounds of approximations to (not necessarily algebraic) numbers and functions.

Today numerical mathematics offers a large variety of stable and reliable algorithms. Erroneous results are very rare, rare enough not to care about that fact all the time, but yet not rare enough to ignore them. The first research direction “Reliable numerical computation” aims to produce rigorously correct answers to numerical problems. This includes to prove that the problem is solvable and to compute mathematically correct error bounds for the solution. Solely floating-point arithmetic is used to take advantage of the tremendous speed, which naturally poses limits on problems which can be solved. However, in contrast to purely numerical methods, no false answers are possible: Either a true error bound is computed or, a corresponding error message is given.

The second research direction “Complexity on the Reals” is a branch of computability theory studying those functions on the real numbers and related structures which can be effectively computed by machines such as digital computers. This is where real analysis meets (discrete) complexity theory with its notions of runtime and memory/space. It is a branch of TTE (“Type 2 Theory of Effectivity”), which has turned out to be particularly useful for investigating computability on uncountable sets. The success of TTE was based on the idea of joining classical computability theory from theoretical computer science with the mathematical field of topological spaces. For practical purposes and in the spirit of algorithm engineering, the asymptotic results from complexity theory are further refined by considering the efficiency of actual implementations in “exact real arithmetic”.

Most of the participants are expected to give presentations on their current research, however the schedule will ensure ample time for discussions and ad hoc sessions. We also plan to hold brainstorming sessions, to discuss unfinished ideas, to present very recent results, and to reflect the current state in general.

As the two groups of researchers currently are working quite independently, it is very hard to predict concrete results. However, we strongly anticipate that the joint meeting will be as fruitful as the join of computability theory and topology when creating TTE.

License
  Creative Commons BY 3.0 DE
  Norbert T. Müller and Siegfried M. Rump and Klaus Weihrauch and Martin Ziegler

Classification

  • Data Structures / Algorithms / Complexity
  • Semantics / Formal Methods
  • Verification / Logic

Keywords

  • Computable analysis
  • Reliable numerical computation
  • Complexity of real computation
  • Floating-point arithmetic
  • Exact real arithmetic

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

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).

Publikationen

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

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.