pipette
ENEnglish

Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples

Gautam Kamath

Preprint

En palabras de los autores

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 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 .

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.