About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ITCS 2013
Conference paper
On the power of conditional samples in distribution testing
Abstract
In this paper we define and examine the power of the conditional sampling oracle in the context of distribution-property testing. The conditional sampling oracle for a discrete distribution μ takes as input a subset S ⊂ [n] of the domain, and outputs a random sample i ∈ S drawn according to μ, conditioned on S (and independently of all prior samples). The conditional-sampling oracle is a natural generalization of the ordinary sampling oracle in which S always equals [n]. We show that with the conditional-sampling oracle, testing uniformity, testing identity to a known distribution, and testing any label-invariant property of distributions is easier than with the ordinary sampling oracle. On the other hand, we also show that for some distribution properties the sample complexity remains near-maximal even with conditional sampling. © 2013 ACM.