School Seminars and Colloquia

The epsilon-net story

Discrete Structures and Algorithms (Seminar)

by Professor Janos Pach

Institution: Renyi Institute (Budapest) and EPFL (Lausanne)
Date: Wed 29th August 2012
Time: 1:00 PM
Location: Old Geology Theatre 2

Abstract: In 1986, Haussler and Welzl introduced the notion of epsilon-nets and adapted a theorem of Vapnik-Chervonenkis to establish the existence of small epsilon-nets in hypergraphs (range spaces) of small "dimension." Since then epsilon-net theory has been successfully applied in machine learning, in discrete and computational geometry and elsewhere. It has been an outstanding open problem to determine the size of the smallest epsilon-net that can be found in every hypergraph. We summarize the last chapter of the story, and describe some recent geometric constructions found by the speaker and by Gabor Tardos.