Columbia Home
Loading Events

« All Events

  • This event has passed.

Discrete Math Seminar

January 28, 2014 @ 3:00 pm - 4:00 pm

Speaker: Esther Ezra (NYU)

Title: Geometric Discrepancy Via the Entropy Method

Abstract: Discrepancy theory, also referred to as the theory of irregularities of distribution, has been developed into a diverse and fascinating field, with numerous closely related areas, including, numerical integration, Ramsey theory, graph theory, geometry, and theoretical computer science, to name a few. Informally, given a set system S defined over an n-item set X, the combinatorial discrepancy is the minimum, over all two-colorings of X, of the largest deviation from an even split, over all sets in S. Since the celebrated \six standard deviations suffice” paper of Spencer in 1985, several long standing open problems in the theory of combinatorial discrepancy have been resolved, including tight discrepancy bounds for halfspaces in d-dimensions [Matousek 1995] and arithmetic progressions [Matousek and Spencer 1996]. 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”.

Details

Date:
January 28, 2014
Time:
3:00 pm - 4:00 pm
Event Category:

Venue

S.W. Mudd, Room 303
303 Mudd
500 W 120th Street,

Organizer

Discrete Math Seminar
Website:
http://www.columbia.edu/~mc2775/seminar.html
Print this page