Geometric Discrepancy and its Applications

24/12/2015 - 12:00

Discrepancy theory has been developed into a diverse and fascinating field, with numerous closely related areas. In this talk, I will survey several classic results in combinatorial and geometric discrepancy and then present discrepancy bounds of two kinds, the first is a size-sensitive bound for geometric set systems (that is, the sets are realized by simply-shaped regions, as halfspaces and balls in d-dimensions), and the second is a discrepancy bound for abstract set systems of low degree, which is a problem motivated by the Beck-Fiala conjecture. Both bounds are nearly-optimal. For the first bound our analysis exploits the so-called "entropy method" and "partial coloring", combined with the existence of small packing numbers, and for the second bound our mechanism exploits the Lovasz Local Lemma.

I will also present the notion of relative approximations, initially introduced in learning theory, and their relation to discrepancy, and will conclude with their applications to approximate range search, geometric optimization and machine learning.