Telling Two Distributions Apart: a Tight Characterization

Eyal Even Dar, Mark Sandler

We consider the problem of distinguishing between two arbitrary black-box distributions defined over the domain [n], given access to $s$ samples from both. It is known that in the…