PreprintCC BY 4.0arXiv
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 ε-far from each other in total variation distance. Our algorithm and lower bound show that Θ̃((log n)/ε2) 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 Θ̃(log n).
Related
- Certified exact bounds for adaptive quantitative group testing with two defectives
- How Many Independent Samples Does a Satellite Image Contain? Generalization Bounds for Spatially Dependent Data
- Identifying Panel Conditioning with Refreshment Samples: Sharp Bounds and Design Assumptions
- Testing Conditional Distribution Equality Using Generative Models
- Equivalence testing and run-count design for stochastic machine-learning experiments
BibTeX
@misc{kamath2026tight,
title = {{Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples}},
author = {Gautam Kamath},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11145},
eprint = {2610.11145},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11145},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
AU - Gautam Kamath
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.11145
UR - https://arxiv.org/abs/2610.11145
AB - 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 ε-far from each other in total variation distance. Our algorithm and lower bound show that Θ̃((log n)/ε^2) 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 Θ̃(log n).
ER -