{"id":"arxiv/2605.23225","url":"https://arxiv.org/abs/2605.23225","tags":["cs.DS","cs.DM","cs.IT","cs.LG","math.ST"],"score":0,"title":"Entropy Equivalence Testing","domain":"cs.DS","source":"arxiv","authors":["Clément L. Canonne","Yash Pote","Jonathan Scarlett","Joy Qiping Yang"],"reviews":0,"subject":"cs.DS","summary":"We introduce the problem of \\emph{entropy equivalence testing} for probability distributions, a relaxation of the well-studied closeness testing problem, where the distribution testing algorithm is now only required to distinguish, given samples from two unknown distributions $p,q$ and a parameter $\\varepsilon \\in(0,1/2]$, between $p=q$ and $|H(p)-H(q)| \\geq \\varepsilon$ (where $H$ denotes the Shannon entropy). We provide a time- and sample-efficient algorithm for this task, showing that the optimal sample complexity for this task can be significantly lower than that of closeness testing. As…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-22","reactions":{}}