Theory of Computing Seminar

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.