Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 5/9 -- Clément Canonne

Weiyun Ma wyma at
Mon May 6 16:53:59 PDT 2019

Hi all,

This Thursday at theory lunch, Clément will tell us about "Distributed goodness-of-fit: when you can't talk much and have little in common." (See abstract below.)

As usual, please join us from noon to 1pm at 463A.


Distributed goodness-of-fit: when you can't talk much and have little in common

Speaker: Clément Canonne

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 Himanshyu Tyagi.



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list