Alladi Ramakrishnan Hall

On the power of conditional sampling: a special case of property testing

Sourav Chakraborty

In the modern world of big data and fast computing, it is essential to design super fast algorithms. Often reading the whole data is either too costly or time-consuming and sometimes not feasible. 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 define 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. In fact we can show that any label-invariant property of distribution can be tested using a constant number of conditional samples. 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 joint works with Kuldeep Meel, Yash Pote, Priyanka Golia and Mate Soos (AAAI19, NeuRIPS20, FMCAD21, CP22) and previous paper with Eldar Fischer, Arie MAtsliah and Yonatan Goldhrish (SICOMP 16)

ISI