Algèbre et géométrie

In statistical learning theory, the notion of VC-dimension was developed by Vapnik and Chervonenkis in the context of approximating probabilities of events by the relative frequency of random test points. This notion has been widely used in combinatorics and computer science, and is also directly connected to model theory through the study of NIP theories. This talk will start with an overview of VC-dimension, with examples motivated by discrete geometry and additive combinatorics. I will then present several model theoretic applications of VC-dimension. The selection of topics will focus on […]

Assume that Q is a relation on R^s of arity s definable in an o-minimal expansion of R. I will discuss how certain extremal asymptotic behaviors of the sizes of the intersections of Q with finite n × ... × n grids, for growing n, can only occur if Q is closely connected to a certain algebraic structure.On the one hand, if the projection of Q onto any s-1 coordinates is finite-to-one but Q has maximal size intersections with some grids (of size >n^(s-1 - ε)), then Q restricted to […]