Post

Clément Canonne
@ccanonne.github.io

New preprint up, led by Joy (Qiping) Yang and Yash Pote, with Jonathan Scarlett: we consider a relaxation of the standard (distribution) closeness testing task, where the algo now only needs to distinguish between p=q (equal) and |H(p)-H(q)|=Ω(1) (their entropies differ). 📝 arxiv.org/abs/2605.23225

arxiv.orgEntropy Equivalence TestingWe 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 no...

3 reposts13 likes

Clément Canonne
@ccanonne.github.io

The algo is quite neat (if I dare say so), with matching lower bounds. But why should you care about this? As as a direct application, we show how to use it as a building block to test whether 2 degree-d Bayes net are the same. Comments welcome (and kudos to Joy and Yash!) arxiv.org/abs/2605.23225

arxiv.orgEntropy Equivalence TestingWe 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 no...
Clément Canonne
@ccanonne.github.io

Thank you, Tom! That's a good question... I don't see an obvious reason why not, though we did not think about it, so there might be. At least the existing building blocks we're using have (iirc) a quantum counterpart, so it should "only" be a matter of checking if the new stuff carries over too.