We study a distributed hypothesis testing problem where two parties observe i.i.d. samples from two ρ-correlated standard normal random variables X and Y. The party that observes the X-samples can communicate R bits per sample to the second party, that observes the Y-samples, in order to test between two correlation values. We investigate the best possible type-II error subject to a fixed type-I error, and derive an upper (impossibility) bound on the associated type-II error exponent. Our techniques include representing the conditional Y-samples as a trajectory of the Ornstein-Uhlenbeck process, and bounding the associated KL divergence using the subadditivity of the Wasserstein distance and the Gaussian Talagrand inequality.

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 ρ of ρ. We show that the best possible performance (optimized over interaction protocol Π and estimator ρ) satisfies infΠ ρsupρE [|ρ−ρ|2] = k−1 (1/2 ln2 + 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 Ω(1/k) rate but with a suboptimal prefactor. Our protocol achieving optimal performance is one-way (non-interactive). We also prove the Ω(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 Ω(n) lower bound on the information complexity of the Gap-Hamming problem, for which we show a direct information-theoretic proof.

Two remotely located agents, Alice and Bob, observe an unlimited number of i.i.d. samples, each of a different part of a Gaussian vector. Alice can send a fixed number of bits on average to Bob, who in turn wants to estimate the correlations between the two parts of the vector. In the case where the agents observe scalar Gaussian random variables with unknown correlation, we obtain two constructive and simple unbiased estimators whose performance coincides with a known but nonconstructive random coding result of Zhang and Berger. In the vector case, which was not treated before, we obtain a nontrivial multidimensional extension that employs the coupling between the correlations to yield better performance. We also discuss application of our technique to cases where the underlying distribution is not fully known.