BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/261
DTSTAMP:20230914T125917Z
SUMMARY:Epsilon-nets and its Relatives
DESCRIPTION:Speaker: Saurabh Ray (Max Planck Institute fur Informatik\nDepa
 rtment 1: Algorithms and Complexity\nCampus E1 4\, Room 319 66123\nSaarbru
 cken Germany)\n\nAbstract: \nEpsilon nets and approximations are among the
  most fundamental notions of sampling. For a given set system and a parame
 ter $\\epsilon$\, an $\\epsilon$-net is a transveral for the sets of size 
 at least $\\epsilon n$\, $n$ being the size of the ground set. The idea or
 iginated in the context of learning theory and was introduced by Haussler 
 and Welzl in 1987. With a delicate use of random sampling\, they showed th
 at any set system of finite VC dimension has an $\\epsilon$-net of small s
 ize independent of the size of the set system - and moreover a random samp
 le of this size is an $\\epsilon$-net with high probability. Epsilon nets 
 are now an important tool that has found applications in many areas includ
 ing computational geometry\, approximation algorithms\, discrepancy theory
  and statistics. Very simple and deterministic constructions were found by
  Matousek in 1991. Deterministic algorithms for computing $\\epsilon$-nets
  have turned them into a general tool for divide & conquer and for derando
 mization - many of the sophisticated data structures and algorithms are ba
 sed on $epsilon$-nets. They power tools like cuttings and simplicial parti
 tions that are among the finest algorithmic tools in geometry. Besides alg
 orithmic applications\, they have have been used for the proof of other co
 mbinatorial results. Recent research on Epsilon nets and related problems 
 has revealed further connections to other areas of mathematics.\n\nIn this
  talk I will give an introduction to $\\epsilon$-nets and the various rela
 ted problems that I have worked on. I will describe my results on the cons
 truction of $\\epsilon$-nets\, related geometric set cover problems\, enum
 eration problems and weak $\\epsilon$-nets.\n
URL:https://www.tcs.tifr.res.in/web/events/261
DTSTART;TZID=Asia/Kolkata:20120327T160000
DTEND;TZID=Asia/Kolkata:20120327T170000
LOCATION:A-269 (DAA Seminar)
END:VEVENT
END:VCALENDAR