We consider the problem of estimating sparse discrete distributions under
local differential privacy (LDP) and communication constraints. We characterize
the sample complexity for sparse estimation under LDP constraints up to a
constant factor and the sample complexity under communication constraints up to
a logarithmic factor. Our upper bounds under LDP are based on the Hadamard
Response, a private coin scheme that requires only one bit of communication per
user. Under communication constraints, we propose public coin schemes based on
random hashing functions. Our tight lower bounds are based on the recently
proposed method of chi squared contractions.

By admin