Dagstuhl Seminar 25131
Weihrauch Complexity: Structuring the Realm of Non-Computability
( Mar 23 – Mar 28, 2025 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/25131
Organizers
- Vasco Brattka (Universität der Bundeswehr - München, DE)
- Alberto Marcone (University of Udine, IT)
- Arno Pauly (Swansea University, GB)
- Linda Westrick (Pennsylvania State University - University Park, US)
Contact
- Michael Gerke (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Dagstuhl Reports
As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.
- Upload (Use personal credentials as created in DOOR to log in)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
This Dagstuhl Seminar is dedicated to the investigation of two active areas of research, one in theoretical computer science, the other in mathematical logic. These are computable analysis on the one hand, and reverse mathematics and applied computability theory on the other. That there is a deep connection between these areas was first suggested by Gherardi and Marcone (2008) and later independently by Dorais, Dzhafarov, Hirst, Mileti, and Shafer (2016) and Hirschfeldt and Jockusch (2016). The past decade has seen this connection blossom into a rich and productive area of research, with by now many papers and several PhD theses dedicated to it. Results in this area fall into two intertwined groups: Some clarify the structure of the degrees of non-computability; some further our understanding of the precise nature of non-computability of particular computational tasks of interest. Grasping the nature of non-computability is a profound goal mirroring the quest to understand the nature of computation. Knowing the degree of non-computability of a computational task brings with it answers as to whether weaker or approximate versions of it might be solvable. This interdisciplinary development was fostered not least by the two precursor Dagstuhl Seminars on this topic. The current seminar will explore recent trends and results, open questions, and new directions of this fascinating field of research that has become known as Weihrauch complexity. These include:
- New interior and closure operators (first-order part of problems, deterministic part of problems etc.)
- Game-theoretic classifications and dichotomies in the Weihrauch lattice
- Analogous of induction and boundedness principles and the Paris-Harrington hierarchy
- New choice principles in the Weihrauch lattice (overt, analytic choice etc.)
- Relations to new categorical and logical approaches (Lawvere-Tierney topologies, instancewise versions of Weihrauch reducibility)
- Global structure of the Weihrauch lattice (chains, antichains, density, etc.)
Creative Commons BY 4.0
Vasco Brattka, Alberto Marcone, Arno Pauly, and Linda Westrick
Please log in to DOOR to see more details.
- Djamel-Eddine Amir (University Paris-Saclay - Orsay, FR)
- Andrej Bauer (University of Ljubljana, SI) [dblp]
- Laurent Bienvenu (CNRS & Université de Bordeaux, Talence, FR) [dblp]
- Vasco Brattka (Universität der Bundeswehr - München, DE) [dblp]
- Merlin Carl (Europa-Universität - Flensburg, DE) [dblp]
- Raphael Carroy (University of Torino, IT) [dblp]
- Vittorio Cipriani (TU Wien, AT)
- Matthew de Brecht (Kyoto University, JP) [dblp]
- Damir D. Dzhafarov (University of Connecticut - Storrs, US) [dblp]
- Johanna N. Y. Franklin (Hofstra University - Hempstead, US) [dblp]
- Anton Freund (Universität Würzburg, DE) [dblp]
- Makoto Fujiwara (Tokyo University of Science, JP) [dblp]
- Giorgio Genovesi (University of Leeds, GB)
- Kenneth Gill (West Chester, US)
- Jun Le Goh (National University of Singapore, SG) [dblp]
- Peter Hertling (Universität der Bundeswehr - München, DE) [dblp]
- Jeffry L. Hirst (Appalachian State University - Boone, US) [dblp]
- Rupert Hölzl (Universität der Bundeswehr - München, DE) [dblp]
- Akitoshi Kawamura (Kyoto University, JP) [dblp]
- Takayuki Kihara (Nagoya University, JP) [dblp]
- Ulrich Kohlenbach (TU Darmstadt, DE) [dblp]
- Davide Manca (Universität Würzburg, DE)
- Alberto Marcone (University of Udine, IT) [dblp]
- Joseph S. Miller (University of Wisconsin - Madison, US) [dblp]
- Daniel Mourad (Nanjing University, CN)
- Carl Mummert (Marshall University - Huntington, US) [dblp]
- Keng Meng Ng (Nanyang TU - Singapore, SG) [dblp]
- Arno Pauly (Swansea University, GB) [dblp]
- Cécilia Pradic (Swansea University, GB) [dblp]
- Emmanuel Rauzy (Universität der Bundeswehr - München, DE)
- Matthias Schröder (TU Darmstadt, DE) [dblp]
- Paul Shafer (University of Leeds, GB) [dblp]
- Giovanni Soldà (Ghent University, BE)
- Mariya I. Soskova (University of Wisconsin - Madison, US) [dblp]
- Ivan Titov (University of Bordeaux, FR)
- Patrick Uftring (Universität Würzburg, DE)
- Manlio Valenti (Swansea University, GB)
- Java Darleen Villano (University of Connecticut - Storrs, US)
- Andrea Volpi (University of Udine, IT)
- Keita Yokoyama (Tohoku University, JP) [dblp]
Related Seminars
- Dagstuhl Seminar 15392: Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis (2015-09-20 - 2015-09-25) (Details)
- Dagstuhl Seminar 18361: Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis (2018-09-02 - 2018-09-07) (Details)
Classification
- Logic in Computer Science
Keywords
- Computability and complexity
- combinatorial problems
- reverse and constructive mathematics
- computable analysis
- Weihrauch reducibility and related reducibilities
