Problem 93: Locally Private Heavy Hitters and Other Problems in Streaming

Suggested by	Graham Cormode
Source	Warwick 2018
Short link	https://sublinear.info/93

The model of Local Differential Privacy (LDP) asks for protocols for information release, so that each user's output meets a differential privacy guarantee. A basic primitive is based on a simple coin-flipping method: when users have one private bit of information, they toss a biased coin, so that with probability $p > 1/2$ the true value is released, and with probability $1-p$ the complement is released. The privacy level is quantified by $\varepsilon = \ln(p/1-p)$.

There has been considerable progress in this area by adapting ideas familiar to the sublinear community: dimensionality reduction, sketching, basis transforms, hashing techniques etc. For example, recent work of Bun, Nelson, and Stemmer [BunNS-18] adapts methods for heavy hitters to the LDP model.

Consequently, the open problem is to address other questions in the LDP model, and to provide lower bounds on what can be achieved under this notion of privacy.