Difference between revisions of "Open Problems:93"
m (Krzysztof Onak moved page Waiting:Heavy Hitters and Other Problems in Streaming to Open Problems:93 without leaving a redirect) |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|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)$. | ||
Latest 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.
