DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.50

Entropy Equivalence Testing

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

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

We introduce the problem of 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 ε ∈ (0,1/2], between p = q and |H(p)-H(q)| ⩾ ε (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 an application, we leverage this result to provide the first non-trivial testing algorithm for (standard) closeness of low-degree Bayesian networks, which significantly improves on either the sample or time complexity of a baseline based on full learning.

Cite as

Clément L. Canonne, Yash Pote, Jonathan Scarlett, and Joy Qiping Yang. Entropy Equivalence Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 50:1-50:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{canonne_et_al:LIPIcs.APPROX/RANDOM.2026.50,
  author =	{Canonne, Cl\'{e}ment L. and Pote, Yash and Scarlett, Jonathan and Yang, Joy Qiping},
  title =	{{Entropy Equivalence Testing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{50:1--50:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.50},
  URN =		{urn:nbn:de:0030-drops-277676},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.50},
  annote =	{Keywords: Entropy, distribution testing, sublinear algorithm, Bayesian network}
}

Search Results

Documents authored by Pote, Yash

Entropy Equivalence Testing

Abstract

Cite as

Thanks for your feedback!

Could not send message