Geometric Discrepancy Via the Entropy Method

Geometric Discrepancy Via the Entropy Method

-
Esther Ezra , NYU
Fine Hall 224

In this talk I will present new discrepancy bounds for set systems of bounded primal shatter dimension, with the property that these bounds are sensitive to the actual set sizes. These bounds are nearly-optimal. Such set systems are abstract, but they can be realized by simply-shaped regions, as halfspaces, balls, and octants in d dimensions, to name a few. Our analysis exploits the so-called Entropy method and the technique of partial coloring, combined with the existence of small packings.