We examine an extension of the usual two-party communication mannequin by which Alice and Bob maintain chance distributions and over domains and , respectively. Their aim is to estimate
to inside additive error for a bounded perform , recognized to each events. We check with this because the distributed estimation downside. Particular circumstances of this downside come up in a wide range of areas together with sketching, databases and studying. Our aim is to know how the required communication scales with the communication complexity of and the error parameter .
The random sampling strategy — estimating the imply by averaging over random samples — requires whole communication, the place is the randomized communication complexity of . We design a brand new debiasing protocol which improves the dependence on to be linear as a substitute of quadratic. Moreover we present higher higher bounds for a number of particular lessons of capabilities, together with the Equality and Higher-than capabilities. We introduce decrease sure methods based mostly on spectral strategies and discrepancy, and present the optimality of lots of our protocols: the debiasing protocol is tight for normal capabilities, and that our protocols for the equality and greater-than capabilities are additionally optimum. Moreover, we present that amongst full-rank Boolean capabilities, Equality is basically the simplest.
- † College of California, Los Angeles
- ‡ College of California, Berkeley
- § Institute for Superior Examine (IAS)
