Recently, there has been significant work studying distribution testing under the Conditional Sampling model. In this model, a query involves specifying 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 primarily study thetolerant versions of the classicuniformity andidentity testing problems, providing improved query complexity bounds in the conditional sampling model. In this paper , we prove that tolerant uniformity testing in the conditional sampling model can be solved using O(\varepsilon^{-2}) queries, which is known to be optimal and improves upon the O(\varepsilon^{-20})-query algorithm of  [CRS15]. Our bound even holds under the Pair Conditional Sampling model, a restricted version of the conditional sampling model where every queried subset S either must have exactly 2 elements, or must be the entire domain of the distribution. We also 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. \tilde{O})-query algorithm for monotonicity testing in the conditional sampling model, improving on the }\tilde{O} ] Finally, we study (non-tolerant) identity testing under the pair conditional sampling model, and provide a tight bound of \tilde{\Theta}( \sqrt{\log n \cdot \varepsilon^{-2}) for the query complexity, improving upon both the known upper and lower bounds in [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 O(\varepsilon^{-2}) queries, which is optimal and improves upon the 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 Can15]. Finally, we study (non-tolerant) identity testing under the pair conditional sampling model, and provide a tight bound of \tilde{\Theta}( \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].
R
involves specifying
specifies
D
primarily study the
D
tolerant
D
versions of the classic
D
uniformity
D
and
D
identity
R
testing problems, providing improved
improve
R
in the conditional sampling model. In this paper
for several classic distribution testing problems in this model. First
D
known to be
A
Canonne et al.
R
Our
This
D
the Pair Conditional Sampling model,
R
where every queried subset S either must have exactly 2 elements, or must be the entire domain of the distribution. We also
called the Pair Conditional Sampling model. Next, we
A
Next, we use our algorithm for tolerant uniformity testing to get an
A
(\varepsilon^{-4
A
(\varepsilon^{-22
A
Can15
A
.
R
\sqrt{\log n
\sqrt{\log N
R
improving
where the domain of the distribution has size N. This improves