Testing Correctness of Samplers Using Property Testing From Theory to Practice and Back Again

Title Of the Talk: “ Testing Correctness of Samplers Using Property Testing: From Theory to Practice and Back Again
Speakers: Prof. Sourav Chakraborty (ISI, Kolkata)
Host Faculty: Dr. Nitin Saurabh
date: : October 16 (Wednesday); 3:30pm – 4:30pm

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 (AAAI 2019) 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 (FMCAD 2022) On Quantitative Testing of Samplers with Kuldeep Meel, Priyanka Golia and Mate Soos (CP 2022) 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)

Speaker Profile:

Bio: Sourav Chakraborty is a Professor in Computer Science at the Indian Statistical Institute, Kolkata, India. He finished his Bachelors in Mathematics from Chennai Mathematical Institute in 2003 and then went on to do his Master’s (in 2005) and Ph.D. (in 2008) in Computer Science from the University of Chicago under the guidance of Prof. Laszlo Babai. After doing one year of postdoc at Technion, Israel, and one year of postdoc at CWI Amsterdam, he joined Chennai Mathematical Institute in 2010. He joined the Indian Statistical Institute in 2018. His main area of interest is Theoretical Computer Science with a particular focus on query complexity, property testing, Fourier Analysis of Boolean functions, streaming algorithms, and graph algorithms. Recently he has been using property testing techniques in other more applied areas.

Date:
October 16 (Wednesday); 3:30pm – 4:30pm

Venue
Auditorium (A block)