cs.DScs.ITstat.ML

Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples

📅 👥 1 authors arXiv:2610.11145v1

Authors

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 $\varepsilon$-far from each other in total variation distance. Our algorithm and lower bound show that $\tilde Θ\left(\frac{\log n}{\varepsilon^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 Θ(\log n)$.

Paper Information

arXiv ID:
2610.11145v1
Published:

Related Categories

cs.DScs.ITstat.ML