Monika Seisenberger has been invited to give a talk at a joint event of the BCTCS 2024 and Southern Logic Seminar in Bath in April 2024. More information about BCTCS 2024 can be found here.
Arno Pauly will give an invited talk at the Leeds Computability Days in July.
Manlio Valenti will give an invited talk at the AMS-UMI International joint meeting (Palermo, July) and at the joint meeting of the New Zealand, Australian and American mathematical societies (Auckland, December).
Manlio Valenti, together with his collaborators David Reed Solomon and Damir Dzhafarov, submitted the paper “The tree pigeonhole principle in the Weihrauch degrees”: https://meetings.ams.org/math/jmm2024/meetingapp.cgi/Paper/29664
We are thrilled to extend a warm welcome to Davide Trotta, a postdoctoral researcher at the Department of Computer Science at the University of Pisa in Italy. Davide brings his knowledge and expertise to our community, and we are excited to have him as a guest speaker in our upcoming seminar series, which will take place on Monday, 4 December in our Theory Lab.
Title: Categorifying computable reducibilities
Abstract: One of the most relevant notions of categorical logic which enabled the study of logic from a purely algebraic perspective is the notion of a (hyper)doctrine, introduced in a series of seminal papers by F.W. Lawvere to synthesize the structural properties of logical systems. In this talk, I will introduce this categorical approach to logic and explain how various notions well-known in computability can be framed within this categorical framework.
In particular, I will present categorical formulations in terms of Lawvere doctrines for the Medvedev, Muchnik, and Weihrauch reducibilities.
Finally, I will discuss some universal properties of such doctrines, showing how this study enables us to identify, from an abstract perspective, the common features of these notions of reducibility.
This talk is based on joint work with Manlio Valenti and Valeria de Paiva.
Computability and Complexity Analysis conference is coming to Swansea next year. It will take place in Computational Foundry on 11-14 July.
Watch this space for more updates.
Next week Giovanni Solda is visiting us from Ghent. He will give a talk on "A combinatorial principle weak over weak systems yet strong over strong systems".
Abstract:
Better quasi orders (henceforth bqos) are a strengthening of the notion of well quasi order. Even if their definition is more complicated, the former enjoy nice closure properties that make them, in a way, easier to work with than the latter: this feature made bqos an instrumental tool in proving landmark results like Nash-Williams' theorem and Laver's theorem. From the reverse mathematical point of view, the study of bqos is an interesting area still full of open questions.
In this talk, we will focus on a property of non-bqos, the so-called minimal bad array lemma, and in particular one version of it that we will call MBA − . We will show that MBA − has a very odd behavior when it comes to its reverse-mathematical strength, namely
• over ATR 0 , MBA − can be seen to be equivalent to the very strong principle of Π 12 -comprehension, yet
• over ACA 0 , MBA − does not imply ATR 0.
In order to prove this result, we will provide a characterization of the quasi-orders that ACA 0 proves to be bqos.
This is joint work with Anton Freund, Alberto Marcone, and Fedor Pakhomov.
BCTCS 2025 at Strathclyde University, Glasgow Marek Jezinski, Alec Critten, Harry Bryant and Olga Petrovska are currently attending the 41st...
