18 July 2023, 10:30-11:30.
ENS, room Emmy Noether, on level -2 of Aile Rataud.
Distinct Elements in Streams: An Algorithm for the (Text) Book
Abstract: Given a data stream of m elements, the Distinct Elements problem is to estimate the number of distinct elements in the stream. Distinct Elements has been a subject of theoretical and empirical investigations over the past 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-efficient algorithm whose description and the proof are accessible to undergraduates with a knowledge of basic probability theory.
In addition to the simplicity, the approach has significant theoretical and practical implications: our approach allowed us to resolve the open problem of (Discrete) Klee’s Measure Problem in the streaming setting and build a state-of-the-art DNF counter in practice.
Relevant publications: PODS-21, PODS-22, ESA-22, IJCAI-23
Short bio: Kuldeep Meel is an Associate Professor of Computer Science in the Department of Computer Science at the University of Toronto. His research interests lie at the intersection of Formal Methods and Artificial Intelligence. He is a recipient of the 2022 ACP Early Career Researcher Award, the 2019 NRF Fellowship for AI, and was named AI’s 10 to Watch by IEEE Intelligent Systems in 2020. His research program’s recent recognition include the 2023 CACM Research Highlight Award, 2022 ACM SIGMOD Research Highlight, IJCAI-22 Early Career Spotlight, 2021 Amazon Research Award, selection to “Best Papers of CAV” (2020 and 2022) special issue in FMSD journal, Best Paper Award nomination at ICCAD-21 and DATE-23, 1st Place in Model Counting Competition (2020, 2022, and 2023).
