Appears in collection : 2016 - T1 - WS4 - Inference problems theme

The bounds on the sample complexity of most fundamental learning and testing problems for discrete distributions are well understood. We consider the scenario in which samples are collected by multiple players who have to communicate in order to solve the learning or testing problem. We ask how much communication this kind of task requires. In the talk, I will focus on the problem of learning the distribution and show that players have to essentially transmit all their samples, provided each of them has a limited number of them.