2026-09-10T09:44:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27767 2026-09-09T12:19:37Z ddc:004 open_access

Entropy Equivalence Testing Canonne, Clément L. Pote, Yash Scarlett, Jonathan Yang, Joy Qiping Entropy distribution testing sublinear algorithm Bayesian network 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Clément L. Canonne and Yash Pote and Jonathan Scarlett and Joy Qiping Yang 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.50 urn:nbn:de:0030-drops-277676 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.50 eng https://creativecommons.org/licenses/by/4.0/legalcode