# Tight Information Complexity of the Coin Problem in the Broadcast Model

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 34 references that are in the map.
- First posted on arXiv 3 Aug 2026.

## Builds on (most cited first, 13 of 13)

- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Detecting Correlations with Little Memory and Communication](https://mlsanity.com/paper/1803.01420/) (2018)
- [Large Deviation Methods for Approximate Probabilistic Inference](https://mlsanity.com/paper/1301.7392/) (2013)
- [Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities](https://mlsanity.com/paper/2206.02765/) (2022)
- [Strong Memory Lower Bounds for Learning Natural Models](https://mlsanity.com/paper/2206.04743/) (2022)
- [Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints](https://mlsanity.com/paper/2301.03566/) (2023)
- [The Sample Complexity of Simple Binary Hypothesis Testing](https://mlsanity.com/paper/2403.16981/) (2024)
- [Tight Bounds for Set Disjointness in the Message Passing Model](https://mlsanity.com/paper/1305.4696/) (2013)
- [Communication Complexity of Estimating Correlations](https://mlsanity.com/paper/1901.09100/) (2019)
- [The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints](https://mlsanity.com/paper/2506.13686/) (2025)
- [A New Information Complexity Measure for Multi-pass Streaming with Applications](https://mlsanity.com/paper/2403.20283/) (2024)
- [A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures](https://mlsanity.com/paper/2603.00770/) (2026)
- [Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy](https://mlsanity.com/paper/2606.07443/) (2026)

## Abstract (arXiv)

We study distributed testing of Ber(α) versus Ber(β) in the broadcast, or shared-blackboard, model. For protocols with constant advantage, we characterise up to universal constant factors the information complexity under either hypothesis for every pair β<α. The characterisation shows that the two information costs can be quite different and identifies three parameter regimes, with optimal protocols based respectively on clean samples, a noisy binary symmetric channel, and an asymmetric Z-channel. The lower bounds rely on a novel mixed Hellinger--Jensen--Shannon inequality that may be of independent interest. We also characterise the constant-advantage information complexity of testing arbitrary discrete distributions via an optimisation problem over channels, and show that binary-output channels suffice. We obtain bounds for bounded likelihood-ratio distributions, and give general upper bounds in terms of chi2 divergence. As applications, we recover the broadcast-model set-disjointness lower bound, and derive stronger lower bounds in the multi-pass streaming setting for some problems considered in prior work.