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.
Short Bio:
Sourav Chakraborty is a Professor of Computer Science at the Indian Statistical Institute (ISI), Kolkata. He earned his bachelor's degree in Mathematics from Chennai Mathematical Institute in 2003, followed by a Master's (2005) and Ph.D. (2008) in Computer Science from the University of Chicago, where he studied under the famous mathematician and computer scientist Prof. László Babai. He pursued postdoctoral research at Technion, Israel, and CWI Amsterdam before joining Chennai Mathematical Institute in 2010 and later moving to ISI in 2018. His primary research interests lie in Theoretical Computer Science.
