BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Distinct Elements in Streams and the Klee's Measure Problem - Sour
 av Chakraborty (ISI)
DTSTART:20250318T140000Z
DTEND:20250318T150000Z
UID:TALK228841@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:The distinct elements problem in streaming algorithms refers t
 o estimating the number of unique elements in a data stream while using li
 mited memory. A generalization of this problem is Klee's Measure Problem\,
  where the goal is to estimate the size of the union of sets when the sets
  arrive in a data stream\, all while using limited memory and having restr
 icted access to the sets.\n\nWhile the distinct elements problem is well-s
 tudied in streaming algorithms\, with tight bounds already established\, K
 lee's Measure Problem has remained a major open problem in the field for m
 any years.\n\nWe will present the first-ever efficient streaming algorithm
  (from PODS '21) for Klee's Measure Problem. This algorithm also provides 
 a remarkably simple streaming solution for the distinct elements estimatio
 n problem\, which even caught the attention of Donald E. Knuth (https://ww
 w-cs-faculty.stanford.edu/~knuth/papers/cvm-note.pdf).\n\nThis talk is bas
 ed on joint works with N. V. Vinodchandran and Kuldeep S. Meel across mult
 iple articles\, notable the following:\n\nEstimating the Size of Union of 
 Sets in Streaming Models. PODS 2021\nEstimation of the Size of Union of De
 lphic Sets: Achieving Independence from Stream Size. PODS 2022\nDistinct E
 lements in Streams: An Algorithm for the (Text) Book. ESA 2022\nImproved S
 treaming Algorithm for the Klee's Measure Problem and Generalizations. (jo
 intly with Mridul Nandi\, Arijit Ghosh and Soumit Pal) APPROX 2024
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR