Dagstuhl Seminar 18361
Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis
( Sep 02 – Sep 07, 2018 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/18361
Organizers
- Vasco Brattka (Universität der Bundeswehr - München, DE)
- Damir D. Dzhafarov (University of Connecticut - Storrs, US)
- Alberto Marcone (University of Udine, IT)
- Arno Pauly (Swansea University, GB)
Contact
- Michael Gerke (for scientific matters)
- Simone Schilke (for administrative matters)
Impacts
- A note on the diamond operator - Westrick, Linda - Cornell University : arXiv.org, 2020. - 5 pp..
- Combinatorial principles equivalent to weak induction : article : 12 pp. - Davis, Caleb; Hirschfeldt, Denis R.; Hirst, Jeffry L.; Jake, Pardo; Pauly, Arno; Keita, Yokoyama - Amsterdam : IOS Press, 2019 - (Computability ; Pre-Press 2019).
- Dagstuhl Seminar on Measuring the Complexity of Computational Content 2018 : Special Issue : pp. 167 - 341 - Brattka, Vasco; Dzhafarov, Damir D.; Marcone, Alberto; Pauly, Arno - Amsterdam : IOS Press, 2020 - (Computability ; 9. 2020. 3/4).
- Leaf management : article : 6 pp. - Hirst, Jeffry L. - Amsterdam : IOS Press, 2019 - (Computability ; Pre-Press 2019).
- Searching for an analogue of ATR in the Weihrauch lattice - Kihara, Takayuki; Marcone, Alberto; Pauly, Arno - Cornell University : arXiv.org, 2018. - 35 pp..
Reducibilities such as many-one, Turing, or polynomial-time reducibility have been an extraordinarily important tool in theoretical computer science from its very beginning. In recent years these reducibilities have been extended to the continuous setting, where they allow us to classify computational problems on real numbers and other continuous data types.
In the late 1980s, Weihrauch introduced a reducibility that can be seen as an analogue of many-one reducibility for (multi-valued) functions on infinite data types. This reducibility, now called Weihrauch reducibility, was studied since the 1990s by Weihrauch's school of computable analysis and really started to flourish after Gherardi and Marcone proposed it as a tool for a uniform approach to reverse analysis.
Another program for studying the complexity of mathematical problems is reverse mathematics, which aims to classify theorems according to the axioms that are needed to prove these theorems in second-order arithmetic. This proog-theoretic approach yields non-uniform classifications of the computational content of theorems. However, many of these classifications also have uniform content and Weihrauch complexity allows us to study this uniform computational content directly using methods of computability theory.
This perspective motivated Dorais, Dzhafarov, Hirst, Mileti and Shafer, on the one hand, and Hirschfeldt and Jockusch, on the other hand, to study combinatorial problems using Weihrauch reducibility. This research has led to a number of further reducibilities (computable reducibility, generalized Weihrauch reducibility and others) that can be seen as non-uniform or less resource sensitive versions of Weihrauch reducibility. Using this toolbox of reducibilities one can now adjust the instruments exactly according to the degree of uniformity and resource sensitivity that one wants to capture. This has led to a number of exciting new ideas and results in what was previously already a very active and fruitful area.
The objectives of and the questions that should be addressed during the Dagstuhl Seminar fall into a number of different categories:
Classification of the Complexity of Problems
One part of the seminar will be devoted to the study of classifications of further computational problems in the Weihrauch lattice. A particular focus of this seminar will be on combinatorial problems such as Ramsey's theorem and variants thereof. Another hot topic of current research is the classification of probabilistic problems in the Weihrauch lattice and the presentation of further new results in this direction is anticipated too.
Higher Levels of the Weihrauch Lattice
A new active area of research is the study of higher levels of the Weihrauch lattice that correspond to the reverse mathematics systems above ACA_0, such as ATR_0. It has emerged that choice on Baire space and its unique counterpart are related to these systems and we expect that promising new research in this area that is currently on its way will be presented and further discussed at the Dagstuhl Seminar.
Structural Properties
We expect that structural and algebraic properties of the Weihrauch lattice will be subject of intensive discussion at the meeting alongside with the presentation of new classification results of specific problems.
Creative Commons BY 3.0 DE
Vasco Brattka, Damir D. Dzhafarov, Alberto Marcone, and Arno Pauly
Reducibilities such as many-one, Turing or polynomial-time reducibility have been an extraordinarily important tool in theoretical computer science from its very beginning. In recent years these reducibilites have been transferred to the continuous setting, where they allow us to classify computational problems on real numbers and other continuous data types.
In the late 1980s Weihrauch has introduced a reducibility that can be seen as an analogue of many-one reducibility for (multi-valued) functions on infinite data types. This reducibility, now called Weihrauch reducibility, was studied since the 1990s by Weihrauch's school of computable analysis and flourished recently when Gherardi and Marcone proposed this reducibility as a tool for a uniform approach to reverse analysis.
Reverse mathematics aims to classify theorems according to the axioms that are needed to prove these theorems in second-order arithmetic. This proof theoretic approach yields non-uniform classifications of the computational content of certain theorems. However, many of these classifications also have uniform content and Weihrauch complexity allows us to study this uniform computational content directly using methods of computability theory.
This perspective has motivated Dorais, Dzhafarov, Hirst, Mileti and Shafer, on the one hand, Hirschfeldt and Jockusch, on the other hand, to study combinatorial problems using this approach. This research has led to a number of further reducibilities (computable reducibility, generalized Weihrauch reducibility and others) that can be seen as non-uniform or less resource sensitive versions of Weihrauch reducibility. Using this toolbox of reducibilities one can now adjust the instruments exactly according to the degree of uniformity and resource sensitivity that one wants to capture.
A precursor seminar (15392 Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis, see https://doi.org/10.4230/DagRep.5.9.77) that was also held at Dagstuhl has been instrumental in bringing together researchers from these different communities for the first time. This has created a common forum and fostered several research developments in this field. We believe that the current seminar was very successful in strengthening and deepening the collaborations between the involved communities. Ample time was left and successfully used for research in groups. A novelty of the current seminar was a special session at which solutions of open problems from the previous seminar were presented. To see that several of the major open problems of the previous meetings were solved in the meantime was inspiring and motivating! Some of the solutions involve new techniques with a wider applicability. Hopefully, we will see solutions to some of the open questions presented at the current seminar in the not too far future! Altogether, the seminar did proceed in a highly productive atmosphere, thanks to many excellent contributions from participants. Inspired by these contributions the organizers are planning to edit a special issue of the journal Computability dedicated to this seminar.
This report includes abstracts of many talks that were presented during the seminar, it includes a list of some of the open problems that were discussed, as well as a bibliography on Weihrauch complexity that was started during the previous meeting and that saw significant growth in the meantime. Altogether, this report reflects the extraordinary success 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!
Vasco Brattka, Damir D. Dzhafarov, Alberto Marcone, and Arno Pauly
- Eric P. Astor (Google - New York, US) [dblp]
- Vittorio Bard (University of Torino, IT)
- Laurent Bienvenu (University of Montpellier & CNRS, FR) [dblp]
- Vasco Brattka (Universität der Bundeswehr - München, DE) [dblp]
- Merlin Carl (Universität Konstanz, DE) [dblp]
- Raphael Carroy (Universität Wien, AT) [dblp]
- Matthew Colbrook (Cambridge University, GB)
- Matthew de Brecht (Kyoto University, JP) [dblp]
- Hannes Diener (University of Canterbury - Christchurch, NZ) [dblp]
- Francois G. Dorais (University of Vermont, US) [dblp]
- Damir D. Dzhafarov (University of Connecticut - Storrs, US) [dblp]
- Marta Fiori Carones (University of Udine, IT)
- Guido Gherardi (University of Bologna, IT) [dblp]
- Jun Le Goh (Cornell University, US) [dblp]
- Peter Hertling (Universität der Bundeswehr - München, DE) [dblp]
- Denis R. Hirschfeldt (University of Chicago, US) [dblp]
- Jeffry L. Hirst (Appalachian State University - Boone, US) [dblp]
- Rupert Hölzl (Bundeswehr University Munich, DE) [dblp]
- Mathieu Hoyrup (LORIA & INRIA Nancy, FR) [dblp]
- Akitoshi Kawamura (Kyushu University, JP) [dblp]
- Takayuki Kihara (Nagoya University, JP) [dblp]
- Ulrich Kohlenbach (TU Darmstadt, DE) [dblp]
- Wei Li (National University of Singapore, SG) [dblp]
- Alberto Marcone (University of Udine, IT) [dblp]
- Kenshi Miyabe (Meiji University - Kawasaki, JP) [dblp]
- Carl Mummert (Marshall University - Huntington, US) [dblp]
- Takako Nemoto (JAIST - Ishikawa, JP) [dblp]
- Eike Neumann (Aston University - Birmingham, GB) [dblp]
- Keng Meng Ng (Nanyang TU - Singapore, SG) [dblp]
- Sabrina Ouazzani (Université Paris-Est Créteil, FR) [dblp]
- Ludovic Patey (University Claude Bernard - Lyon, FR) [dblp]
- Arno Pauly (Swansea University, GB) [dblp]
- Cristóbal Rojas (Universidad Andres Bello - Santiago, CL) [dblp]
- Matthias Schröder (Universität der Bundeswehr - München, DE) [dblp]
- Victor Selivanov (A. P. Ershov Institute - Novosibirsk, RU) [dblp]
- Paul Shafer (University of Leeds, GB) [dblp]
- Giovanni Soldà (University of Leeds, GB)
- Florian Steinberg (INRIA Sophia Antipolis, FR) [dblp]
- Patrick Uftring (TU Darmstadt, DE)
- Manlio Valenti (University of Udine, IT)
- Klaus Weihrauch (FernUniversität in Hagen, DE) [dblp]
- Linda Westrick (Pennsylvania State University - University Park, US) [dblp]
- Keita Yokoyama (JAIST - Ishikawa, JP) [dblp]
Related Seminars
Classification
- data structures / algorithms / complexity
- verification / logic
Keywords
- Computability and complexity
- combinatorial problems
- reducibilities
- computational complexity
- reverse and constructive mathematics
