BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1268
DTSTAMP:20230914T125957Z
SUMMARY:Estimating the size of union of sets in streaming model
DESCRIPTION:Speaker: Sourav Chakraborty (ISI Kolkata)\n\nAbstract: \nWe pre
sent a very simple and efficient sampling-based algorithm for estimating t
he union of sets in the streaming setting. Suppose we have a collection of
sets S_1\, . . . \, S_M subsets of T\, arriving one by one in a stream\;
the sets are not given explicitly to us but rather defined implicitly via
the following oracles: for each set\, we can know the size of the set\, ge
t a uniform sample from the set\, and given a point check whether it belon
gs to the set. The goal is to estimate the size of the union of the sets S
_1\, . . . \, S_M.\nWe present a simple algorithm that estimates the size
of the union\, upto a (1 + \\epsilon) factor\, in space complexity and upd
ate time complexity O(log(M)^2/\\epsilon^2).\nOur algorithm provides the f
irst algorithm with polynomial dependence on the dimension for Klee’s me
asure problem in streaming setting and independent of the stream size\, th
ereby settling the open problem of Woodruff and Tirthpura (PODS-12).\nThis
talk will be based on works with Kuldeep Meel and Vinodchandran (PODS21\,
PODS22 and ESA22).\n
URL:https://www.tcs.tifr.res.in/web/events/1268
DTSTART;TZID=Asia/Kolkata:20230127T160000
DTEND;TZID=Asia/Kolkata:20230127T170000
LOCATION:A201
END:VEVENT
END:VCALENDAR