Computer Science Theory Seminar

Jayadev AcharyaCornell University
Statistical Inference Under Local Information Constraints

Monday, April 22, 2019 - 4:00pm
Gates 122 or Bloomberg 497 at NY Tech

Abstract: We start by asking the following puzzle. Independent samples from an unknown distribution p on {1, …, k} are distributed across n players, with each player holding one sample. Each player can communicate L bits to a central referee, who wants to simulate a sample from p. When L= log k, one player suffices, since they can send their sample to the referee. How many players are needed to enable simulation if each player can only send L