Sharp Bounds for Generalized Uniformity Testing

We establish tight bounds on the sample complexity of generalized uniformity testing. In more detail, we present a computationally efficient tester whose sample complexity is optimal, within constant factors, and a matching worst-case information-theoretic lower bound. Specifically, we show that the sample complexity of generalized uniformitytestingisΘ 1/( 4/3kpk3)+1/( 2kpk2) .