Computer Science Theory Seminar
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