Colloquium Details
Epsilon-nets and Related Problems
Speaker: Saurabh Ray, Max-Planck-Institut Informatik
Location: Warren Weaver Hall 1302
Date: February 27, 2013, 11:30 a.m.
Host: Dennis Shasha
Synopsis:
Since their introduction by Haussler and Welzl in 1987, Epsilon Nets have become a central tool in computational geometry and have found several applications in approximation algorithms, discrepancy theory and statistics. Deterministic algorithms for computing Epsilon Nets have turned them into a general tool for divide & conquer and for derandomization - many of the sophisticated data structures and algorithms are based on Epsilon Nets. They power tools like cuttings and simplicial partitions that are among the finest algorithmic tools in geometry. Besides algorithmic applications, they have also been used for proving combinatorial results. Recent research on Epsilon nets and related problems has revealed further connections to other areas of mathematics.
I will give a brief introduction to Epsilon nets and the some of the related problems that I have worked on. I will focus mainly on an algorithm for approximating minimum hitting sets.
Notes:
In-person attendance only available to those with active NYU ID cards.