A New Approach for Testing Properties of Discrete Distributions

Understand

In this work, we give a novel general approach for distribution testing.

• We describe two techniques: our first technique gives sample-optimal testers, while our second technique gives matching sample lower bounds.
• As a consequence, we resolve the sample complexity of a wide variety of testing problems.
• Our upper bounds are obtained via a modular reduction-based approach.