Communication Complexity of Distributed High Dimensional Correlation Testing

DOI10.1109/TIT.2021.3091773MaRDI QIDQ4958286zbMATH OpenOpenAlexFDO

Authors K. R. Sahasranand, Himanshu Tyagi

Publication date 7 September 2021

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.10571

zbMATH Keywords

correlated Gaussian random variablestwo-party distributed hypothesis testing

Mathematics Subject Classification ID

Parametric hypothesis testing (62F03) Communication theory (94A05)

Abstract: Two parties observe independent copies of a $d$-dimensional vector and a scalar. They seek to test if their data is correlated or not, namely they seek to test if the norm $|ho{|}_2$ of the correlation vector $ho$ between their observations exceeds $au$ or is it $0$. To that end, they communicate interactively and declare the output of the test. We show that roughly order $d/a{u}^2$ bits of communication are sufficient and necessary for resolving the distributed correlation testing problem above. Furthermore, we establish a lower bound of roughly $d^2/a{u}^2$ bits for communication needed for distributed correlation estimation, rendering the estimate-and-test approach suboptimal in communication required for distributed correlation testing. For the one-dimensional case with one-way communication, our bounds are tight even in the constant and provide a precise dependence of communication complexity on the probabilities of error of two types.

Cited in

(2)

• Correlation in Hard Distributions in Communication Complexity
• Computing the correlation dimension on a network of workstations

This page was built for publication: Communication Complexity of Distributed High Dimensional Correlation Testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4958286)