Open Problems:93 - Revision history

Krzysztof Onak: Krzysztof Onak moved page Waiting:Heavy Hitters and Other Problems in Streaming to Open Problems:93 without leaving a redirect

2019-08-20T03:49:51Z

Krzysztof Onak moved page Waiting:Heavy Hitters and Other Problems in Streaming to Open Problems:93 without leaving a redirect

Krzysztof Onak: Updating the header

2019-08-20T03:49:40Z

Updating the header

Ccanonne at 22:06, 7 August 2019

2019-08-07T22:06:14Z

Ccanonne: Created page with "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..."

2019-08-07T22:03:46Z

Created page with "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..."

New page

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 {{Cite|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.

@@ Line 1: / Line 1: @@
 {{Header
 |source=warwick18
 |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)$.

← Older revision		Revision as of 22:06, 7 August 2019
Line 1:		Line 1:
		+	{{Header
		+	\|title=Locally Private Heavy Hitters and Other Problems in Streaming
		+	\|source=warwick18
		+	\|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)$.

← Older revision	Revision as of 03:49, 20 August 2019
(No difference)