Name
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1137/140964199 | SIAM J. Comput. |
Keywords | DocType | Volume |
distribution testing,distribution-property testing,conditional-sampling oracle,prior sample,conditional sampling oracle,distribution property,conditional sample,conditional sampling,discrete distribution,ordinary sampling oracle,known distribution,random sample i | Journal | 45 |
Issue | ISSN | Citations |
4 | 0097-5397 | 6 |
PageRank | References | Authors |
0.51 | 13 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sourav Chakraborty | 1 | 381 | 49.27 |
| eldar fischer | 2 | 815 | 63.82 |
| Yonatan Goldhirsh | 3 | 13 | 2.32 |
| Arie Matsliah | 4 | 249 | 24.98 |