Spring 2017

A Notion of VC-dimension for Subsets of Groups – Analysis, Combinatorics and Structure

Wednesday, Jun. 20, 2018 10:15 am10:45 am

Add to Calendar

The VC-dimension of a family sets, named after Vapnik and Chervonenkis, is an interesting combinatorial concept that has been used in machine learning, computational geometry and the theory of empirical processes. In this talk we shall discuss a notion of VC-dimension for subsets of groups and discuss the structure of subsets of abelian groups with bounded VC-dimension -- illustrating what might be termed an arithmetic regularity lemma -- as well as some analytic results about convolutions. These results can be used to give strong answers to classical additive combinatorial questions, such as finding structures in sumsets, in the bounded-VC setting.