Los Angeles Combinatorics and Complexity Seminar: Sauer–Shelah–Perles lemma for lattices

Tuesday, November 24, 2020 at 9:30am to 10:00am

This is a past event.
Virtual Event

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).

Dial-In Information

Zoom Meeting: https://ucla.zoom.us/j/96564290758

Meeting ID: 965 6429 0758
Passcode: Please see your email for the passcode to join via Zoom

Warning: You must be registered under your name to be admitted.

Event Type

Lecture / Talk / Workshop

Add this to your calendar

Recent Activity