The Price of Tolerance in Distribution Testing

Clément L. Canonne, Ayush Jain, Gautam Kamath +1

We revisit the problem of tolerant distribution testing. That is, given samples from an unknown distribution $p$ over $\{1,\dots ,n\}$, is it ${\epsilon }_1$-close to or $\varepsi…