BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1344
DTSTAMP:20231030T132223Z
SUMMARY:Distinct Elements in Streams: An algorithm for the (text) book
DESCRIPTION:Speaker: Kuldeep S. Meel (University of Toronto)\n\nAbstract: \
nGiven a data stream of m elements\, the Distinct Elements problem is to e
stimate the number of distinct elements in the stream. Distinct Elements h
as been a subject of theoretical and empirical investigations over the pas
t four decades resulting in space-optimal algorithms for it. However\, all
the current state-of-the-art algorithms are often difficult to analyze or
impractical.I will present a simple\, intuitive\, sampling-based space-ef
ficient algorithm whose description and the proof are accessible to underg
raduates with a knowledge of basic probability theory.In addition to the s
implicity\, the approach has significant theoretical and practical implica
tions: our approach allowed us to resolve the open problem of (Discrete) K
lee's Measure Problem in the streaming setting and build a state-of-the-ar
t DNF counter in practice.\n
URL:https://www.tcs.tifr.res.in/web/events/1344
DTSTART;TZID=Asia/Kolkata:20231128T100000
DTEND;TZID=Asia/Kolkata:20231128T113000
LOCATION:via Zoom in A201
END:VEVENT
END:VCALENDAR