{"id":"arxiv/2610.18723","url":"https://arxiv.org/abs/2610.18723","tags":["cs.IT","cs.DS","math.ST"],"score":0,"title":"Optimal Support Size Testing","domain":"cs.IT","source":"arxiv","authors":["Qisheng Wang"],"reviews":0,"subject":"cs.IT","summary":"We present an optimal tester for support size that determines whether an unknown probability distribution is supported on $n$ elements or $\\varepsilon$-far away (in total variation distance) with sample complexity $Θ(\\frac{n}{\\varepsilon\\log(n)})$, improving the prior best $O(\\frac{n}{\\varepsilon\\log(n)} \\log(\\min\\{\\frac{1}{\\varepsilon}, n\\}))$ due to Ferreira Pinto Jr. and Harms (STOC 2025). As a generalization, we provide a pretty good lower bound on support size.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-13","reactions":{}}