Timezone: »

Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters
Jayadev Acharya · Ziteng Sun

Tue Jun 11 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #177
We consider the problems of distribution estimation, and heavy hitter (frequency) estimation under privacy, and communication constraints. While the constraints have been studied separately, optimal schemes for one are sub-optimal for the other. We propose a sample-optimal $\eps$-locally differentially private (LDP) scheme for distribution estimation, where each user communicates one bit, and requires \emph{no} public randomness. We also show that Hadamard Response, a recently proposed scheme for $\eps$-LDP distribution estimation is also utility-optimal for heavy hitters estimation. Our final result shows that unlike distribution estimation, without public randomness, any utility-optimal heavy hitter estimation algorithm must require $\Omega(\log n)$ bits of communication per user.

Author Information

Jayadev Acharya (Cornell University)
Ziteng Sun (Cornell/Google)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors