The Role of VC-dimension in Discrete Geometry

Orateur:	MUSTAFA Nabil
Localisation:	ESIEE, France
Type:	Groupe de travail analyse, probabilités et statistique
Site:	UGE
Salle:	3B081
Date de début:	10/03/2015 - 10:30
Date de fin:	10/03/2015 - 10:30

A very useful way to capture the complexity of a set-system is its VC-dimension. In this talk I will explain the use of VC-dimension in getting improved bounds for several geometric problems, both combinatorial (epsilon-nets, discrepancy) as well as algorithmic (set-cover, nearest neighbors).