Collection Nexus Trimester - 2016 - Inference Problems Theme
Organizer(s)
Date(s)
28/04/2024
Communication Complexity of Learning Discrete Distributions
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.
