Abstract
We study a recently introduced framework for property testing of probability distributions, by considering distribution testing algorithms that have access to a conditional sampling oracle. This is an oracle that takes as input a subset S of the domain [N]={1,2,...,N} of the unknown probability distribution D and returns a draw from the conditional probability distribution D restricted to S. This model allows considerable flexibility in the design of distribution testing algorithms; in particular, testing algorithms in this model can be adaptive.
The talk will survey a range of results on testing probability distributions with a conditional sampling oracle and compare what is achievable in this framework versus the standard framework (in which algorithms can only draw i.i.d. samples from the unknown distribution). We will see that testinga lgorithms in the conditional sample framework can be significantly more efficient than in the standard framework: for many testing problems where poly(N) many draws from D are required to solve the problem in the standard framework, there are conditional sampling algorithms that require only poly(log N, 1/epsilon) calls to the conditional oracle (or sometimes even just poly(1/epsilon) calls to the conditional oracle independent of N).
Joint work with Clement Canonne and Dana Ron.