Sauer–Shelah–Perles lemma for lattices
Yuval Filmus (Technion, Haifa, Israel)
Abstract: The Sauer–Shelah–Perles (SSP) lemma is a fundamental result in VC theory, with important applications in statistical learning theory. It bounds the number of sets in a family in terms of the size of the universe and the VC dimension. We generalize the SSP lemma to some lattices, such as the lattice of subspaces of a finite-dimensional vector space over a finite field. The SSP lemma fails for some lattices, and we identify a local obstruction which we conjecture is the only reason for such failure.
The talk will not assume any familiarity with VC theory or with statistical learning theory.
Joint work with Stijn Cambie (Raboud University Nijmegen), Bogdan Chornomaz (Vanderbilt University), Zeev Dvir (Princeton University) and Shay Moran (Technion).
computer science theorycombinatorics
Audience: researchers in the discipline
LA Combinatorics and Complexity Seminar
Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm
| Organizers: | Igor Pak*, Greta Panova |
| *contact for this listing |