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