BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/553
DTSTAMP:20230914T125929Z
SUMMARY:Size-sensitive Packing Number for the Hamming Cube and its Conseque
 nces
DESCRIPTION:Speaker: Kunal Dutta (Max-Planck-Institut fur Informatik\nDepar
 tment 1: Algorithms and Complexity\nCampus E1 4\, Room 319\n66123 Saarbruc
 ken\nGermany)\n\nAbstract: \nAbstract: An abstract set system\, or hypergr
 aph\, consists of a universe (here assumed finite)\, together with a subse
 t of its power set. A set-system is $\\delta$-separated if any pair of its
  constituent subsets have symmetric difference at least $\\delta$. In 1992
 \, Haussler proved an optimal upper bound on the packing number for $\\del
 ta$-separated set systems having bounded primal shatter dimension. A set s
 ystem with bounded primal shatter dimension is said to have \\emph{size-se
 nsitive shattering constants} $d_1$ and $d_2$\, if the number of distinct 
 projections of the system on any subset of its universe having $m$ element
 s\, is at most $O(m^{d_1}k^{d_2})$.\nWe prove a size-sensitive version of 
 Haussler’s Packing lemma [Hau92] for set-systems with bounded primal sha
 tter dimension\, which have an additional size-sensitive property. This an
 swers a question asked by Ezra [Ezr14]. As a consequence of this result we
  get an improvement on the discrepancy bounds for set systems with the abo
 ve size sensitive property. Improved bound on the discrepancy for these sp
 ecial set systems also implies an improvement in the size of $(\\nu\, \\al
 pha)$-samples (and relative $(\\varepsilon\,\\delta)$-approximations) (joi
 nt work with Arijit Ghosh\, Max-Planck-Institute\, Saarbrücken).\n
URL:https://www.tcs.tifr.res.in/web/events/553
DTSTART;TZID=Asia/Kolkata:20141205T140000
DTEND;TZID=Asia/Kolkata:20141205T153000
LOCATION:AG-69
END:VEVENT
END:VCALENDAR