Abstract: How can one test the correctness of a program that is supposed to output an element from a large universe according to a certain distribution? These kinds of programs are heavily used in real life but are rarely tested for correctness.

This problem can be framed as a problem in property testing. Property testing is a subject that deals with these challenges. It tries to design sub-linear algorithms for testing various properties of inputs. The key lies in the way the data is accessed by the algorithm.

One of the central problems in property testing and many other related subjects is testing if a distribution has a certain property – say whether a distribution on a finite set is uniform. The conventional way of accessing the distributions is by drawing samples according to the distributions. Unfortunately, in this setting the number of samples that are necessary for testing properties of distribution (for most natural properties) is polynomial in the size of support of the distribution. Thus when the support is relatively big the algorithms become impractical in real life applications.

We introduced a new way of accessing the distribution using “conditional-sampling oracle". This oracle can be used to design much faster algorithms for testing properties of distribution and thus makes the algorithm useful in practical scenarios.

We show that the conditional oracle can be implemented in many real life problems and we have been able to show the usefulness of this model and our algorithms in practical purposes and in other areas of research – like testing of probabilistic verification. This model also throws a number of interesting theoretical questions.

The talk will be based on the following works:
On the Power of Conditional Samples in Distribution Testing with Eldar Fischer, Arie MAtsliah and Yonatan Goldhrish (SICOMP 2016)
Property Testing of Joint Distributions using Conditional Samples with Rishiraj Bhattacharyya (ToCT 2018)
On Testing of Uniform Samplers with Kuldeep Meel (AAAI2019)
On Testing of Samplers with Kuldeep Meel and Yash Pote (NeuRIPS 2020)
Designing Samplers is Easy: The Boon of Testers with Kuldeep Meel, Priyanka Golia and Mate Soos (FMCAD22)
On Quantitative Testing of Samplers with Kuldeep Meel, Priyanka Golia and Mate Soos (CP22)
Testing of Horn Samplers with Ansuman Banerjee, Shayak Chakraborty, Sayantan Sen, Uddalok Sarkar and Kuldeep Meel (AISTAT 2023)
Tight Lower Bound on Equivalence Testing in Conditional Sampling Model with Diptarka Chakraborty and Gunjan Kumar (SODA 2024)
Testing Self-Reducible Samplers with Rishiraj Bhattacharyya, Yash Pote, Uddalok Sarkar and Sayantan Sen (AAAI 2024)

About the Speaker: Sourav Chakraborty is a Professor in the Advanced Computing and Microelectronics Unit (ACMU) of the Computer and Communication Sciences Division (CCSD) at the Indian Statistical Institute (ISI), Kolkata, India. Before joining ISI on July 2018 he was a faculty member at Chennai Mathematical Institute , India, from September 2010. Before that he was a postdoc at the Algorithms and Complexity department of Centrum Wiskunde & Informatica (CWI), Amsterdam, Netherlands from September 2009 to August 2010. From October 2008 to August 2009 he was a postdoc at the Computer Science Department of Technion, Israel. In June 2008 he finished his PhD in Computer Science from University of Chicago under the supervision of Prof. László Babai.

His field of research is Theoretical Computer Science. His focus has been in the classical and quantum complexity of Boolean functions (including property testing, sensitivity and block sensitivity of Boolean functions and quantum database search), in electronic commerce, in graph algorithms and in coding theory.