# Inference under Information Constraints II: Communication Constraints and Shared Randomness

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2019.

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

- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities](https://mlsanity.com/paper/2206.02765/) (2022)
- [Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints](https://mlsanity.com/paper/2301.03566/) (2023)
- [Differentially Private Sampling from Distributions](https://mlsanity.com/paper/2211.08193/) (2022)
- [The Sample Complexity of Simple Binary Hypothesis Testing](https://mlsanity.com/paper/2403.16981/) (2024)
- [The Role of Interactivity in Structured Estimation](https://mlsanity.com/paper/2203.06870/) (2022)
- [Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests](https://mlsanity.com/paper/2406.06749/) (2024)
- [Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes](https://mlsanity.com/paper/2604.07796/) (2026)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [Robust Testing and Estimation under Manipulation Attacks](https://mlsanity.com/paper/2104.10740/) (2021)
- [Continual Mean Estimation Under User-Level Privacy](https://mlsanity.com/paper/2212.09980/) (2022)
- [An invitation to the sample complexity of quantum hypothesis testing](https://mlsanity.com/paper/2403.17868/) (2024)
- [Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2509.21940/) (2025)
- [Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints](https://mlsanity.com/paper/2106.08597/) (2021)
- [Optimal high-dimensional and nonparametric distributed testing under communication constraints](https://mlsanity.com/paper/2202.00968/) (2022)
- [Collaborative Learning of Discrete Distributions under Heterogeneity and Communication Constraints](https://mlsanity.com/paper/2206.00707/) (2022)
- [Statistical Inference with Limited Memory: A Survey](https://mlsanity.com/paper/2312.15225/) (2023)
- [Uniformity Testing in the Shuffle Model: Simpler, Better, Faster](https://mlsanity.com/paper/2108.08987/) (2021)
- [On Collaboration in Distributed Parameter Estimation with Resource Constraints](https://mlsanity.com/paper/2307.06442/) (2023)
- [Relatively Smart: A New Approach for Instance-Optimal Learning](https://mlsanity.com/paper/2603.01346/) (2026)
- [Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model](https://mlsanity.com/paper/2606.07124/) (2026)
- [Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compression](https://mlsanity.com/paper/2609.36610/) (2026)

## Abstract (arXiv)

A central server needs to perform statistical inference based on samples that are distributed over multiple users who can each send a message of limited length to the center. We study problems of distribution learning and identity testing in this distributed inference setting and examine the role of shared randomness as a resource. We propose a general-purpose simulate-and-infer strategy that uses only private-coin communication protocols and is sample-optimal for distribution learning. This general strategy turns out to be sample-optimal even for distribution testing among private-coin protocols. Interestingly, we propose a public-coin protocol that outperforms simulate-and-infer for distribution testing and is, in fact, sample-optimal. Underlying our public-coin protocol is a random hash that when applied to the samples minimally contracts the chi-squared distance of their distribution to the uniform distribution.