Date/Time : 26 Nov 2025 17:00
Venue : S17 #04-04 (Seminar Room 3)
Speaker : Leonardo Nagami Coregliano, University of Chicago

In the Netflix Prize Competition (2006–2009), we are given a finite set $U$ of users, a finite set $M$ of movies and a partial function $f: U\times M\rightharpoonup R$, where $f(u,m)$ indicates how user $u$ rates movie $m$ and we are tasked with completing $f$ to a total function to predict how all users $U$ rate all movies in $M$. Although some algorithms did fairly well in the competition, giving a satisfactory theoretical explanation for their success has been difficult.

In this talk I will discuss how this learning problem can be seen as an instance of a framework that we call “sample completion learning” and how sample completion learning is completely characterized by the model-theoretic notion of $k$-dependence introduced by Shelah (which can be seen as a high-dimensional version of the Vapnik–Chervonenkis dimension). In turn, this gives a full theoretical characterization of when the Netflix problem is “solvable”.

Add to calendar :

Date/Time : 12 Nov 2025 17:00
Venue : S17 #05-11 (Seminar Room 5)
Speaker : Daniel Mourad, Nanjing University

We characterize the continuous-Weihrauch-least problem that is discontinuous on a countable set of Cantor-Bendixson (CB) rank alpha. Consider the following conceptualization of CB rank: Suppose that X is a countable subset of Baire space and that x is an element of X which you want to write down. Call x your target. Suppose that while writing down x via increasing initial segments you decide to switch your target to a different element of X that is compatible with what you have already written. The Cantor-Bendixson rank of x in X is an ordinal alpha keeping track of how many times you may switch your target after committing to arbitrarily long initial segments in between each target switch. Applying this conceptualization to Weihrauch problems leads to the intuition that a multifunction P being discontinuous on a set of Cantor-Bendixson rank alpha tells us that, when showing P is discontinuous, we can diagonalizing against the continuous functions in steps counting down from alpha. We formalize this notion and prove the following result.

The problem of all-or-co-unique choice on the natural numbers (ACC_N) can be thought of as the problem of diagonalizing a single time. Building on work of Pauly and Soldà, we show that a specific notion of solving ACC_N within alpha many attempts is the continuous-Weihrauch-least problem discontinuous on a countable subset X of its domain such that all points in X have CB rank at most alpha.

Add to calendar :

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 :