# Communication Complexity of Estimating Correlations

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2019.

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

- [Trade-offs in Data Memorization via Strong Data Processing Inequalities](https://mlsanity.com/paper/2506.01855/) (2025)
- [Statistical Inference with Limited Memory: A Survey](https://mlsanity.com/paper/2312.15225/) (2023)
- [Batches Stabilize the Minimum Norm Risk in High Dimensional Overparameterized Linear Regression](https://mlsanity.com/paper/2306.08432/) (2023)
- [Tight Information Complexity of the Coin Problem in the Broadcast Model](https://mlsanity.com/paper/2608.02776/) (2026)

## Abstract (arXiv)

We characterize the communication complexity of the following distributed estimation problem. Alice and Bob observe infinitely many iid copies of ρ-correlated unit-variance (Gaussian or ±1 binary) random variables, with unknown ρ∈[-1,1]. By interactively exchanging k bits, Bob wants to produce an estimate hatρ of ρ. We show that the best possible performance (optimized over interaction protocol Pi and estimator hat ρ) satisfies infPi hatρsupρ mathbbE [|ρ-hatρ|2] = tfrac1k (frac12 ln 2 + o(1)). Curiously, the number of samples in our achievability scheme is exponential in k; by contrast, a naive scheme exchanging k samples achieves the same Omega(1/k) rate but with a suboptimal prefactor. Our protocol achieving optimal performance is one-way (non-interactive). We also prove the Omega(1/k) bound even when ρ is restricted to any small open sub-interval of [-1,1] (i.e. a local minimax lower bound). Our proof techniques rely on symmetric strong data-processing inequalities and various tensorization techniques from information-theoretic interactive common-randomness extraction. Our results also imply an Omega(n) lower bound on the information complexity of the Gap-Hamming problem, for which we show a direct information-theoretic proof.