***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Date: Thursday 18th April, 4:30 in Fine Hall 224.
 
Speaker: Esther Ezra (NYU)

Title: On Relative Approximations in Geometric Hypergraphs.

Abstract: Motivated by range counting problems, relative approximations have
become a central tool in computational geometry. In fact, they were introduced
by Har-Peled and Sharir, who derived them from the seminal work of Li, Long, 
and Srinivasan in the theory of machine learning. In this talk I will discuss
properties of relative approximations, and present improved upper bounds for
their size under certain favorable assumptions. Our approach is probabilistic,
where we apply the constructive version of the Asymmetric Lovasz Local Lemma.

                       -----------

Next week: TBA

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)