Aryaman Jal: VC dimension, epsilon nets, and the art gallery problem
Tid: Fr 2021-11-12 kl 13.15 - 14.00
Plats: KTH, 3721 and Zoom (meeting ID: 68578498723)
Medverkande: Aryaman Jal (KTH)
Abstract
The VC dimension of a set system is an important measure of its complexity and has found applications in computational and discrete geometry, statistics and more recently, additive combinatorics. We present a condensed introduction to the concept in a discrete geometry setting and exhibit its connection to generating small epsilon nets by random sampling. The proof of this is a classic application of the probabilistic method. If time permits, we'll also mention an application to the art gallery problem. The talk will be self-contained and no prior knowledge of discrete geometry will be required.