# The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints

arXiv: https://arxiv.org/abs/2506.13686 · HTML: https://mlsanity.com/paper/2506.13686/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2025.

## Built on by (most cited first, 3 of 3)

- [Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?](https://mlsanity.com/paper/2607.02896/) (2026)
- [Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more](https://mlsanity.com/paper/2606.11469/) (2026)
- [Tight Information Complexity of the Coin Problem in the Broadcast Model](https://mlsanity.com/paper/2608.02776/) (2026)

## Abstract (arXiv)

This paper resolves two open problems from a recent paper, arXiv:2403.16981, concerning the sample complexity of distributed simple binary hypothesis testing under information constraints. The first open problem asks whether interaction reduces the sample complexity of distributed simple binary hypothesis testing. In this paper, we show that sequential interaction does not help. The second problem suggests tightening existing sample complexity bounds for communication-constrained simple binary hypothesis testing. We derive optimally tight bounds for this setting and resolve this problem. Our main technical contributions are: (i) a one-shot lower bound on the Bayes error in simple binary hypothesis testing that satisfies a crucial tensorisation property; (ii) a streamlined proof of the formula for the sample complexity of simple binary hypothesis testing without constraints, first established in arXiv:2403.16981; and (iii) a reverse data-processing inequality for Hellinger-λ divergences, generalising the results from arXiv:1812.03031 and arXiv:2206.02765.