分布式估计的通信复杂性

我们研究了标准双方通信模型的扩展，Alice和Bob分别持有概率分布p和q，目标是在加性误差ε内估计已知函数f的期望值。该问题在草图、数据库和学习等领域有广泛应用。我们关注通信量与函数复杂性及误差参数之间的关系。