One of the primary theoretical tools in machine learning is Vapnik-Chervonenkis dimension (VC dimension), which measures the maximum number of distinct data points a hypothesis set can distinguish. This concept is primarily used in assessing the effectiveness of training classification algorithms from data, and it is established that having finite VC dimension guarantees uniform versions of the various laws of large numbers, in the sense of e.g. Dudley (2014). An important result of Laskowski (1992) showed that finite VC dimension corresponds to a logical notion independently developed by Shelah, known as the non-independence property, and in subsequent decades much work has been done on finite VC dimension within model theory under the aegis of so-called NIP theories (cf. Simon, 2015).

However, despite this deep connection to logic, there has been little done on the computable model theory of VC dimension (one recent exception being Andrews and Guingona, 2016). The basic questions here are the following: (1) how computationally difficult is it to detect that one is in a setting with finite VC dimension?, and (2) if one is in this situation, how hard is it to compute what the precise VC dimension is? The current paper aims to answer these questions and discuss their implications.

Reference

Andrews, U. and Guingona, V. (2016). A local characterization of VC-minimality. Proceedings of the American Mathematical Society, 144(5):2241–2256.

Dudley, R. M. (2014). Uniform central limit theorems, volume 142 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, New York, second edition.

Laskowski, M. C. (1992). Vapnik-Chervonenkis classes of definable sets. Journal of the London Mathematical Society, 45(2):377–384.

Simon, P. (2015). A Guide to NIP Theories. Lecture Notes in Logic. Cambridge University Press, Cambridge.

Classification problems occur in all areas of mathematics. Descriptive set theory provides methods to assign complexity to such problems. Using a technique developed by Hjorth, Kechris and Sofronidis proved, for example, that the problem of classifying all unitary operators $\mathcal{U}(\mathcal{H})$ of an infinite dimensional Hilbert space up to unitary equivalence $\simeq_U$ is strictly more difficult than classifying graph structures with domain $\mathbb{N}$ up to isomorphism.

 
We present a game--theoretic approach to anti--classification results for orbit equivalence relations and use this development to reorganize conceptually the proof of Hjorth's turbulence theorem.  We also introduce a dynamical criterion for showing that an orbit equivalence relation is not Borel reducible to the orbit equivalence relation induced by a CLI group action; that is, a group which admits a complete left invariant metric (recall that, by a result of Hjorth and Solecki, solvable groups are CLI). We deduce that $\simeq_U$ is not classifiable by CLI group actions.

This is a joint work with Martino Lupini.  

We explore the applications of the pcf theory to cardinal estimates.

Mutual stationarity is a notion of infinite products of stationary sets introduced by Foreman and Magidor. The assertion that an infinite sequence of stationary sets is mutually stationary has a natural model theoretic interpretation and can be viewed as a strengthening of the Loewenheim-Skolem property.

We investigate various aspects of compactness of \omega_1 under ZF+ DC (the Axiom of Dependent Choice). We say that \omega_1 is X-supercompact if there is a normal, fine, countably complete nonprincipal measure on \powerset_{\omega_1}(X) (in the sense of Solovay). We say \omega_1 is X-strongly compact if there is a fine, countably complete nonprincipal measure on \powerset_{\omega_1}(X). A long-standing open question in set theory asks whether (under ZFC) "supercompactness" can be equiconsistent with "strong compactness. We ask the same question under ZF+DC. More specifically, we discuss whether the theories "\omega_1 is X-supercompact" and "\omega_1 is X-strongly compact" can be equiconsistent for various X. The global question is still open but we show that the local version of the question is false for various X. We also discuss various results in constructing and analyzing canonical models of AD^+ + \omega_1 is X-supercompact.