Séminaire de Combinatoire de Lyon à l'ENS

Some applications of Vapnik-Cervonenkis dimension.

by Stéphan Thomassé

Amphi A (Site Monod)

Amphi A

Site Monod


Under which condition sampling a bounded set S of individuals can faithfully represent a population? A natural definition for faithfulness is that any property which is verified by x% of the population is also verified by (close to) x% of the sampled individuals. This seemingly hard question has a remarkably simple answer: a population can be faithfully sampled if its VC-dimension is bounded. This parameter ranks among the best measures of structural complexity: it is elegant, easy to use, apply to all sort of objects (matrices, graphs, polynomials, etc), and provides surprisingly short and powerful solutions to many problems.

In this talk, I will give an introduction to VC-dimension and illustrate how it can be used in several areas such as approximation algorithms, counting structures, coloring graphs and voting questions.