Difference between revisions of "Open Problems:93"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Updating the header)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Locally Private Heavy Hitters and Other Problems in Streaming
 
 
|source=warwick18
 
|source=warwick18
 
|who=Graham Cormode
 
|who=Graham Cormode
 
}}
 
}}
 
 
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)$.
 
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)$.
  

Revision as of 03:49, 20 August 2019

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.