Seminar Announcement
Date: Friday, 30 May 2025
Time: 10.30 - 11.30 AM
Venue: Lecture Hall 202
Assessing the Quality of Binomial Samplers: A Statistical Distance Framework
Sourav Chakraborty
ISI Kolkata.
30-05-25

---

Abstract

Randomized algorithms depend on accurate sampling from probability distributions, as their correctness and performance hinge on the quality of the generated samples. However, even for common distributions like Binomial, exact sampling is computationally challenging, leading standard library implementations to rely on heuristics. These heuristics, while efficient, suffer from approximation and system representation errors, causing deviations from the ideal distribution. Although seemingly minor, such deviations can accumulate in downstream applica- tions requiring large-scale sampling, potentially undermining algorithmic guarantees. We will take a look at this often overlooked issue related to correctness of randomized algorithms and have a discussion on what we can do to address this issue?

This is a joint work with Kuldeep Meel and Uddalok Sarkar. This work will appear in CAV 2025.