2025/11/26 by Parikshit Gopalan, Gopalan, Parikshit, Raghu Meka +7
Computer Science · #Complexity and Algorithms in Graphs #Machine Learning and Algorithms #Cryptography and Data Security
paper · pdf · doi:10.48550/arxiv.2511.21015
We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions p and q over domains X and Y, respectively. Their goal is to estimate 𝔼x ∼ p, y ∼ q[f(x, y)] to within additive error ε for a bounded function f, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of f and the error parameter ε. The random sampling approach -- estimating the mean by averaging f over O(1/ε2) random samples -- requires O(R(f)/ε2) total communication, where R(f) is the randomized communication complexity of f. We design a new debiasing protocol which improves the dependence on 1/ε to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.