arXiv preprint ·
Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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)$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Language Modeling is Monotone Compression
DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedback
A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits
JEPA-kMMVAE: CSI Prediction for Time-Varying Wireless Channels
Gaussian BROJA Partial Information Decomposition in Closed Form
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.