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

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
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.