skip to main content

Theory of Computing Seminar

Thursday, May 30, 2019
12:00pm to 1:00pm
Add to Cal
Annenberg 322
Distributed goodness-of-fit: when you can't talk much and have little in common
Clement Canonne, Postdoctoral Scholar, Computer Science, Stanford University,

Abstract: Consider n low-battery sensors, spread across the city, performing each an independent measurement in order to allow a central server to detect changes in the distribution of temperature. For concreteness, suppose the measurements are quantized and take values in {1,2,..,k}: due to the battery and throughput constraints, the sensors can only send L << log k bits each, in one-way fashion, to the server.

Previous work of Acharya, Canonne, and Tyagi [ACT'18] established optimal protocols to perform distributed goodness-of-fit (identity testing) task under these communication constraints; further, they showed a quantitative separation between private-coin protocols (where each sensors can only use its own private coin flips) and public-coin ones (where they share a common random seed, e.g., hardcoded or broadcast by the central server ahead of time). In this work, we refine the question and ask how this quantitative gap behaves with the amount of shared random bits, which we see as an additional resource: namely, we fully characterize the optimal sample complexity of distributed identity testing as a function of k, L, and the number of shared random bits s.

A key aspect of our protocols is a derandomization lemma which we strongly believe to be of independent interest, as well as a generalization of the lower bound framework of [ACT'18] to account for limited shared randomness.

Joint work with Jayadev Acharya, Yanjun Han, Ziteng Sun, and Himanshu Tyagi.

For more information, please contact Bonnie Leung by email at [email protected].