Model Counting Meets Distinct Estimation

Explore the intersection of model counting and distinct element estimation in this 39-minute lecture by Kuldeep Singh from the National University of Singapore. Delve into the similarities between algorithmic frameworks for model counting and F0 computation, uncovering new insights by bridging these seemingly disparate fields. Learn about a simple recipe for translating F0 estimation algorithms to model counting, and discover how distributed streaming algorithms can be transformed for distributed model counting. Examine the framing of F0 estimation as a special case of #DNF counting, revealing a general approach for a wide range of streaming problems. Gain insights from this award-winning research, which received the 2022 ACM SIGMOD Research Highlight Award and 2023 CACM Research Highlights.

Model Counting Meets Distinct Estimation