Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-154 | 8th April 2014 16:21

On the Power of Conditional Samples in Distribution Testing

RSS-Feed




Revision #1
Authors: Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah
Accepted on: 8th April 2014 16:21
Downloads: 565
Keywords: 


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 $\mu$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $\mu$, 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.


Paper:

TR12-154 | 31st October 2012 15:20

On the Power of Conditional Samples in Distribution Testing





TR12-154
Authors: Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah
Publication: 14th November 2012 20:20
Downloads: 1701
Keywords: 


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 $\mu$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $\mu$, 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.



ISSN 1433-8092 | Imprint