VC Dimensions and Regularity - Yuval Wigderson скачать в хорошем качестве

VC Dimensions and Regularity - Yuval Wigderson

Computer Science/Discrete Mathematics Seminar II 10:30am|Simonyi 101 and Remote Access Topic: VC Dimensions and Regularity Speaker: Yuval Wigderson Affiliation: ETH Zürich Date: March 03, 2026 The regularity lemma says that every discrete object can be partitioned into a small number of random-like subobjects. But how small is small? And can we make small smaller if we assume that our given object is simple? And what does it mean for a discrete object to be simple? In this talk, I will answer some of these questions. Along the way, I will discuss many variants and generalizations of the classical notion of VC dimension, which turn out to be essential for answering the questions above. Based on joint work with Lior Gishboliner and Asaf Shapira.