Date/Time : 05 Nov 2025 17:00
Venue : S17 #05-11 (Seminar Room 5)
Speaker : Linus Richter, National University of Singapore

I prove two theorems which classify the complexity of certain sets of Borel codes. These are especially useful in the recursive construction of sets of reals in which Borel codes take on the role of “requirements”; our theorems show that certain classical constructions of sets of reals cannot be straightforwardly effectivised.

Add to calendar :

Date/Time : 15 Oct 2025 17:00
Venue : S17 #05-11 (Seminar Room 5)
Speaker : Luca San Mauro, University of Bari

Borel reducibility has been a decisive tool in assessing whether familiar classes of countable structures can be neatly classified. However, when the corresponding isomorphism problems admit only countably many isomorphism types, they all share the same Borel complexity. To study such cases, we propose a finer framework, inspired by algorithmic learning theory. In this setting, a countable family of countable structures is learnable exactly when its isomorphism problem continuously reduces to E0 (the relation of eventual agreement on reals). Replacing E0 with other equivalence relations then yields a natural hierarchy for ranking isomorphism problems that escape the Borel analysis. Within this framework, we investigate both classical benchmark relations and those arising from established learning criteria. We also revisit the Friedman-Stanley tower from a learning-theoretic viewpoint. This talk is based on a series of joint works with N. Bazhenov, V. Cipriani, E. Fokina, S. Jain, A. Marcone, and F. Stephan.

Add to calendar :

Date/Time : 17 Sep 2025 17:00
Venue : S17 #05-11 (Seminar Room 5)
Speaker : Andrea Volpi, University of Udine

This is joint work with Damir Dzhafarov and Reed Solomon. A relational structure is strongly indivisible if for every partition M = X0 ⊔ X1, the induced substructure on X0 or X1 is isomorphic to M. Cameron (1997) showed that a graph is strongly indivisible if and only if it is the complete graph, the completely disconnected graph, or the random graph. We analyze the strength of Cameron’s theorem using tools from computability theory and reverse mathematics. We show that Cameron’s theorem is is effective up to computable presentation, and give a partial result towards showing that the full theorem holds in the ω-model REC. We also establish that Cameron’s original proof makes essential use of the stronger induction scheme IΣ2.

Add to calendar :

Date/Time : 10 Sep 2025 17:00
Venue : S17 #05-11 (Seminar Room 5)
Speaker : Frank Stephan, National University of Singapore

Degtev constructed in 1976 recursively enumerable many-one degrees with the following properties: no least one-one degrees inside the many-one degree; one least but no minimal one-one degree inside the many-one degree; for each natural number k one least and above the least k minimal one-one degrees inside the given many-one degree (which, of course, depends on k). He did not provide a recursively enumerable many-one degree with infinitely many minimal one-one degrees and Odifreddi put it in 1981 as an open question into his survey paper. According to Batyrshin, the question was in 2021 still open. This talk will now provide the construction of such a many-one degree with infinitely many minimal one-one degrees. Such a degree has a least one-one degree below them. This is joint work with Sanjay Jain, Linus Richter, Samuel Alfaro Tanuwijaya and Xiaoyan Zhang; a write-up is under preparation.

Add to calendar :

Date/Time : 27 Aug 2025 17:00
Venue : S17 #05-11 (Seminar Room 5)
Speaker : Yang Yue, National University of Singapore

I will talk about Halpern-Läuchli Theorem (HL) and its proof(s). This is an ongoing project with Chong Chitat and Li Wei, aiming to find the proof-theoretic strength of HL. I will sketch a proof that under Σ3-induction, there is a computable solution for HL.

Add to calendar :

Date/Time : 20 Aug 2025 17:00
Venue : S17 #05-11 (Seminar Room 5)
Speaker : Tran Chieu Minh, National University of Singapore

In the classic paper “ Henselianity implies large’’ , Pop showed that a field is large if it is elementarily equivalent to the fraction field of a proper Henselian local domain. We show that it can, in fact, be improved to an “if and only if’’ statement.

We will explain how this result arises from the effort to introduce  canonical topologies over a field, namely, a result comparing the etale-open topology with a newly introduced finite-closed topology. (Joint with Will Johnson, Erik Walsberg, and Jinhe Ye)

Add to calendar :

Date/Time : 13 Aug 2025 17:00
Venue : S17 #05-11 (Seminar Room 5)
Speaker : Kenny Gill, La Salle University

A countable structure S is indivisible if it satisfies a pigeonhole principle: for any bounded coloring of any presentation of S, there is a monochromatic induced substructure isomorphic to S. This naturally gives rise to an instance-solution problem Ind(S) which outputs such a substructure given a presentation and coloring. We seek to understand both (1) the computational difficulty of solving Ind(S) for various specific S; and (2) how properties of S can translate to properties of Ind(S) and vice versa. This talk will survey what is known about both (1) and (2), highlighting some of the many open problems in the area. In particular, we propose several notions of uniform embeddability of one structure in another which allow one to obtain desirable properties of Ind(S) for large classes of S. This is in part ongoing joint work with Damir Dzhafarov and Reed Solomon.

Add to calendar :

Date/Time : 16 Apr 2025 17:00
Venue : S17 #04-04 (SR3)
Speaker : Isabella Scott,

Ziegler-reducibility (written ≤*) was introduced by Martin Ziegler in his investigations into finitely generated subgroups of existentially closed (e.c.) groups. It is a refinement of both enumeration- and Turing-reducibility and agrees with Q-reducibility on the c.e. sets. Remarkably, Ziegler showed that it can be characterised purely algebraically: for finitely generated G and H, W(H) ≤* W(G) if and only if H embeds in every e.c. group containing G.

In this talk, I shall discuss the connections between computability theory and existentially closed groups, and recent work on the structure of the Ziegler degrees. In particular, we show that there is a minimal Ziegler degree, and, generalising this construction, that the 3-quantifier theory of the Ziegler degrees is undecidable.

This is joint work with Steffen Lempp and Josiah Jacobsen-Grocott.

Add to calendar :

Date/Time : 09 Apr 2025 17:00
Venue : S17 #04-04 (SR3)
Speaker : Frank Stephan, National University of Singapore

For an unfriendly partition, one colours the nodes of a graph using k colours (mostly, k in {2,3}) such that for each two distinct colours a,b and each node of colour a, this node has more neighbours of colour b than of colour a. If one requires “strictly more” then the colouring is called “strictly
unfriendly” and if one requires “more or at least as many” then the colouring is just called “unfriendly”. The sets of the the nodes of each colour form then a partition of the graph. For two colours, one knows that every finite graph has an unfriendly partition while for countable graphs this is an open problem and for uncountable graphs, this is false, as shown by Shelah and Milner [1990]. Joint work with Belanger, Cipriani, Goh, Richter
and Tang shows that for certain recursive graphs, constructing an unfriendly colouring with two colours cannot be solved by any hyperarithmetic oracle, though a more complicated colouring still exists. Thus one cannot expect to find an easy algorithm solving the task and this might be one of the reasons that the problem is still open. Haynes, Hedetniemi and Vasylieva [2015] showed that for two colours, even finite graphs might fail to have a strictly unfriendly colouring. Indeed, it is shown that constructing strictly unfriendly colourings for two or three colours on finite graphs requires, under the Exponential Time Hypothesis, exponential time. Furthermore, one can reduce the problem 3occur3SAT with n variables to the problem of finding an unfriendly colouring of a finite graph with n’ nodes such that the lower bound c^n for 3occur3SAT translates into the lower bound (c^2/11)^n’. These constant c is not explicitly known, but under the assumption ETH it is strictly between 1 and 2. If one only considers graphs of bounded degree, also nontrivial bounds on the runtime can be obtained. Similar results are obtained for three colours. This is joint work with Sanjay Jain and Haoyun Tang. Furthermore, the three authors joint with Ong Weng Qi investigated the complexity of finding unfriendly colourings for two or three colours when for some nodes some colours are preassigned. This was known to be NP-hard, but the finegrained complexity was not studied before.

Add to calendar :