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)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
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 Ph.D. 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 explored recent trends and results, open questions, and new directions of this fascinating field of research that has become known as Weihrauch complexity. The main part of each day was taken up by regular talks, with extra time set aside for two sessions devoted to open questions and new research directions, as well as plenty of opportunities for less structured socialization and collaboration. Although the ratio of number of talks to number of open questions (as represented in the sessions and this report) was nominally greater than in the previous seminar from 2018, a number of the talks themselves focused heavily on enumerating open questions and outlining future work, and indeed the field has only widened in the intervening years. To mention just a few highlights: investigations of the Weihrauch complexity of reverse-mathematical principles have continued to spur new developments, and this was reflected accordingly in many of the talks here, representing the study of "new" principles as well as new light still being shed on old ones. Important progress has also been made in our understanding of the properties of the Weihrauch lattice itself, such as the existence of uncountable chains and antichains and the density of the Weihrauch degrees above the identity map. Operators on Weihrauch degrees were a prominent theme during the seminar, featuring in the sessions on open problems and new research directions as well as being central to several talks. A few talks concerned recent work to place Weihrauch reducibility in context as an instance of a more general sort of object in category or topos theory.
Last but not least, underscoring the increasingly interdisciplinary interest in this subject, a well-attended joint evening session was spontaneously planned with the concurrent Dagstuhl Seminar 25132 "Approximation Algorithms for Stochastic Optimization"(https://www.dagstuhl.de/25132) in which a speaker from each seminar gave an expository talk aimed at the other's participants: Kevin Schewior spoke about approximate sampling algorithms for stochastic function evaluation, and Arno Pauly about the non-computability of finding Nash equilibria.
This report includes the abstracts of all talks and other presentations given during the seminar (except for the joint talks), along with the most recent version of a bibliography on Weihrauch complexity which was begun during the first Dagstuhl Seminar on the topic in 2015. Altogether, this report reflects the high degree of productivity of our seminar, and we would like to use this opportunity to thank all participants for their valuable contributions and the Dagstuhl staff for their excellent support!
Creative Commons BY 4.0
Vasco Brattka, Alberto Marcone, and Arno Pauly
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.)
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) [dblp]
- 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) [dblp]
- Mariya I. Soskova (University of Wisconsin - Madison, US) [dblp]
- Ivan Titov (University of Bordeaux, FR)
- Patrick Uftring (Universität Würzburg, DE) [dblp]
- Manlio Valenti (Swansea University, GB) [dblp]
- 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
