Abstract: Consider the following questions:
Can we approximate a graph by another graph of constant size?
Can we approximately guess a set knowing only which elements of a finite sample belong to it?
For a collection of sets, can we find a constant-sized subcollection of them such that every set in the collection is close to one of the sets in the subcollection?
Given an infinite collection of subsets of a given probability space, can we get a uniform law of large numbers for the collection?
Given a collection of sets, what is the maximum number of patterns that they can generate on $m$ points?
These apparently unrelated questions are actually all connected and are characterized by the Vapnik--Chervonenkis dimension. In this talk, I will survey these connections and talk about recent extensions of the above questions and concepts to high-dimensional versions.
No background in regularity lemmas, model theory or learning theory will be required. This talk is based on joint works with Maryanthe Malliaris and Caroline Terry.
Bio: Dr. Leonardo Nagami Coregliano received his Ph.D. in Computer Science and Mathematics from the University of Chicago in 2021. He is currently an L. E. Dickson Instructor at the University of Chicago in the Department of Mathematics.