Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
The paper establishes tight bounds for equivalence testing using non-adaptive conditional samples (NACOND). It proves that Θ˜ log n ε 2 queries are both necessary and sufficient for equivalence testing, uniformity, and identity. This means the sample complexity for these fundamental tests under NACOND is all Θ(log n), demonstrating a significant reduction in required samples compared to other sampling models.