Rutgers Discrete Mathematics Seminar

Title: Geometric Discrepancy Via the Entropy Method

Speaker: Esther Ezra, Courant Institute, NYU

Date: Tuesday, March 25, 2014 2:00pm

Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ


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 delta-packings.