Collision-based Testers are Optimal for Uniformity and Closeness

Ilias Diakonikolas, Themis Gouleakis, John Peebles +1

We study the fundamental problems of (i) uniformity testing of a discrete distribution, and (ii) closeness testing between two discrete distributions with bounded ${\ell }_2$-norm. Th…