On the power of Conditional Sampling

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.

In a couple of recent ongoing projects, 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 others areas of research. This model also throws a number of interesting theoretical questions.