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}
}

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.13

A Fast Binary Splitting Approach to Non-Adaptive Group Testing

Authors: Eric Price and Jonathan Scarlett

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

Abstract

In this paper, we consider the problem of noiseless non-adaptive group testing under the for-each recovery guarantee, also known as probabilistic group testing. In the case of n items and k defectives, we provide an algorithm attaining high-probability recovery with O(k log n) scaling in both the number of tests and runtime, improving on the best known O(k² log k ⋅ log n) runtime previously available for any algorithm that only uses O(k log n) tests. Our algorithm bears resemblance to Hwang’s adaptive generalized binary splitting algorithm (Hwang, 1972); we recursively work with groups of items of geometrically vanishing sizes, while maintaining a list of "possibly defective" groups and circumventing the need for adaptivity. While the most basic form of our algorithm requires Ω(n) storage, we also provide a low-storage variant based on hashing, with similar recovery guarantees.

Cite as

Eric Price and Jonathan Scarlett. A Fast Binary Splitting Approach to Non-Adaptive Group Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{price_et_al:LIPIcs.APPROX/RANDOM.2020.13,
  author =	{Price, Eric and Scarlett, Jonathan},
  title =	{{A Fast Binary Splitting Approach to Non-Adaptive Group Testing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.13},
  URN =		{urn:nbn:de:0030-drops-126165},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.13},
  annote =	{Keywords: Group testing, sparsity, sublinear-time decoding, binary splitting}
}

Search Results

Documents authored by Scarlett, Jonathan

Entropy Equivalence Testing

Abstract

Cite as

A Fast Binary Splitting Approach to Non-Adaptive Group Testing

Abstract

Cite as

Thanks for your feedback!

Could not send message