Optimal Support Size Testing

Abstract

We present an optimal tester for support size that determines whether an unknown probability distribution is supported on $n$ elements or $\epsilon$-far away (in total variation distance) with sample complexity $\Theta (\frac{n}{\epsilon \log (n)})$, improving the prior best $O(\frac{n}{\epsilon \log (n)}\log (\min \{\frac{1}{\epsilon },n\}))$ due to Ferreira Pinto Jr. and Harms (STOC 2025). As a generalization, we provide a pretty good lower bound on support size.

arXiv comment12 pages