论文标题
条件采样模型中的分布测试
On Distribution Testing in the Conditional Sampling Model
论文作者
论文摘要
最近，在条件采样模型下进行了大量工作研究分布测试。在此模型中，查询指定了该域的子集$ s $，并且收到的输出是从分配中绘制的样本，条件为$ s $。在本文中，我们改善了该模型中几个经典分布测试问题的查询复杂性界限。 首先，我们证明，可以使用$ \ tilde {o}（\ varepsilon^{ - 2}）$查询来解决条件抽样模型中的耐受性均匀性测试，该测试是最佳的，并且在$ \ tilde {o}（O}（O}（\ varepsilon^{ - 20}）$ -20}）$ algor上是最佳的，并且可以改进。 [CRS15]。该界限甚至在条件采样模型的受限版本下包含，称为对条件采样模型。接下来，我们证明，有条件采样模型中的耐受性身份测试可以在$ \ tilde {o}（\ varepsilon^{ - 4}）$查询中求解，这是第一个已知的已知绑定，独立于该问题的分布的支持大小。接下来，我们使用算法进行耐受性测试，以获得$ \ tilde {o}（\ varepsilon^{ - 4}）$ - 查询算法在条件采样模型中进行单调性测试，以改进$ \ tilde {o}（o v varepsilon^comin^uson^ - query and）。 [CAN15]。最后，我们研究了对条件采样模型下的（不耐受）身份测试，并提供了$ \tildeθ（\ sqrt {\ log n} \ cdot \ cdot \ cdot \ varepsilon^{ - 2}）$的紧密界限，以使查询复杂性，其中分布的域具有尺寸$ n $ $ n $。这在[CRS15]中已知的上限和下限都改善。
Recently, there has been significant work studying distribution testing under the Conditional Sampling model. In this model, a query specifies a subset $S$ of the domain, and the output received is a sample drawn from the distribution conditioned on being in $S$. In this paper, we improve query complexity bounds for several classic distribution testing problems in this model. First, we prove that tolerant uniformity testing in the conditional sampling model can be solved using $\tilde{O}(\varepsilon^{-2})$ queries, which is optimal and improves upon the $\tilde{O}(\varepsilon^{-20})$-query algorithm of Canonne et al. [CRS15]. This bound even holds under a restricted version of the conditional sampling model called the Pair Conditional Sampling model. Next, we prove that tolerant identity testing in the conditional sampling model can be solved in $\tilde{O}(\varepsilon^{-4})$ queries, which is the first known bound independent of the support size of the distribution for this problem. Next, we use our algorithm for tolerant uniformity testing to get an $\tilde{O}(\varepsilon^{-4})$-query algorithm for monotonicity testing in the conditional sampling model, improving on the $\tilde{O}(\varepsilon^{-22})$-query algorithm of Canonne [Can15]. Finally, we study (non-tolerant) identity testing under the pair conditional sampling model, and provide a tight bound of $\tildeΘ(\sqrt{\log N} \cdot \varepsilon^{-2})$ for the query complexity, where the domain of the distribution has size $N$. This improves upon both the known upper and lower bounds in [CRS15].
