Computer Science/Discrete Mathematics Seminar II
VC Dimensions and Regularity
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.
Date & Time
March 03, 2026 | 10:30am – 12:30pm
Add to calendar
03/03/2026 10:30
03/03/2026 12:30
Computer Science/Discrete Mathematics Seminar II
use-title
Topic: VC Dimensions and Regularity
Speakers: Yuval Wigderson, ETH Zürich
More: https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-seminar-ii-614
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.
Simonyi 101 and Remote Access
a7a99c3d46944b65a08073518d638c23
Location
Simonyi 101 and Remote AccessSpeakers
Yuval Wigderson, ETH Zürich