Entropy Equivalence Testing

Clément L. Canonne; Yash Pote; Jonathan Scarlett; Joy Qiping Yang

Entropy Equivalence Testing

Clément L. Canonne, Yash Pote, Jonathan Scarlett, Joy Qiping Yang

arXivarxiv/2605.23225May 22, 2026cs.DSscore 0

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…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.23225
curl -X POST /api/v1/records/arxiv/2605.23225/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.23225/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'