Tight Information Complexity of the Coin Problem in the Broadcast Model
TL;DR
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.
Abstract
We study distributed testing of $\mathrm{Ber}(\alpha)$ versus $\mathrm{Ber}(\beta)$ 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 $\beta<\alpha$. 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 $\chi^2$ 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.