Roland Walker : VC Dimension, VC Density, and the Sauer-Shelah Dichotomy - Part I

Posted by Roland Walker , part of the Louise Hay Logic Seminar.

At

Sept. 21, 2017, 1 p.m.

In

SEO 427

Abstract

Vapnik-Chervonenkis dimension and density are two measures of combinatorial complexity which arose from the study of probability theory. During this two-part talk, we will discuss these measures and their duals both in the classical and model-theoretic contexts, prove the famous Sauer-Shelah Lemma, discuss the relationship between VC dimension and NIP, and time permitting discuss some recent applications and open questions.