Tight Information Complexity of the Coin Problem in the Broadcast Model
We study distributed testing of $\mathrm{Ber}(α)$ versus $\mathrm{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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.02776
curl -X POST /api/v1/records/arxiv/2608.02776/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.02776/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'