Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples

Abstract

We study distribution testing with access to non-adaptive conditional samples. Specifically, we give tight bounds for equivalence testing, determining whether two unknown distributions are equal to or $\epsilon$-far from each other in total variation distance. Our algorithm and lower bound show that $\tilde{\Theta }\left(\frac{\log n}{{\epsilon }^2}\right)$ queries are necessary and sufficient for this problem. These results demonstrate that the complexity of uniformity, identity, and equivalence testing with non-adaptive conditional samples are all $\tilde{\Theta }(\log n)$.