ECCC-Report TR12-154https://eccc.weizmann.ac.il/report/2012/154Comments and Revisions published for TR12-154en-usTue, 08 Apr 2014 16:21:20 +0300
Revision 1
| On the Power of Conditional Samples in Distribution Testing |
Sourav Chakraborty,
Eldar Fischer,
Yonatan Goldhirsh,
Arie Matsliah
https://eccc.weizmann.ac.il/report/2012/154#revision1In 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.Tue, 08 Apr 2014 16:21:20 +0300https://eccc.weizmann.ac.il/report/2012/154#revision1
Paper TR12-154
| On the Power of Conditional Samples in Distribution Testing |
Sourav Chakraborty,
Eldar Fischer,
Yonatan Goldhirsh,
Arie Matsliah
https://eccc.weizmann.ac.il/report/2012/154In 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.Wed, 14 Nov 2012 20:20:41 +0200https://eccc.weizmann.ac.il/report/2012/154