A learning theory approach to noninteractive database privacy

By Avrim Blum, Katrina Ligett, Aaron Roth. 2013

369 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Statistical Learning Theory, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical Learning Theory

In Privacy & Security

Citations in the corpus

Tight Lower Bounds for Locally Differentially Private Selection (2018, background): “ mechanism is one of the most fundamental tools for analyzing high-dimensional datasets subject to differential privacy, and has numerous application: PAC learning [KLN+08], synthetic data generation [BLR13], frequent itemset mining [BLST10], feature selection and sparse regression [TS13, TTZ15, LCS”
Tight Lower Bounds for Differentially Private Selection (2017, background): “Selection problems appear in many natural statistical problems, including private multiple hypothesis testing [1], sparse linear regression [2], [3], finding frequent itemsets [4], and as subroutines in algorithms for answering exponentially many statistical queries [5], [6], [7], [8], [9], approxim”
The Composition Theorem for Differential Privacy (2013, background): “Count queries are well studied in differential privacy [3], [6], [13], [14] and they provide a primitive for constructing more complex queries [3].”
Differentially Private Password Frequency Lists (2016, positive): “[4] showed that the exponential mechanism could be used to answer large classes of queries accurately provided that the dimension of the dataset was reasonably small and that the number of records in the dataset was large7.”
Privacy via the Johnson-Lindenstrauss Transform (2012, methodology): “[7] answer half space queries in the non-interactive setting using a perturbed Johnson-Lindenstrauss projection.”
Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication (2018, background): “Diﬀerential Privacy (DP) [24] has emerged as one of the most popular notions of privacy (see [24, 46, 26, 9, 36, 32], references therein, and the recent book [25]).”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, background): “, 2006) has emerged as one of the most popular notions of privacy (see (Dwork et al., 2006; Wasserman & Zhou, 2010; Blum et al., 2013; McSherry & Talwar, 2007; Kairouz et al., 2017), references therein, and the recent book (Dwork & Roth, 2014)).”
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy (2013, methodology): “Most related to our work is the work on private learning and its sample complexity [22, 6, 3, 9] and the early work on sanitization [7].”
Make Up Your Mind: The Price of Online Queries in Differential Privacy (2016, methodology): “Then we can apply a differentially private algorithm that gives good accuracy as long as the data universe has subexponential size [Blum et al., 2013].”
Simultaneous Private Learning of Multiple Concepts (2015, background): “One surprising result in differential privacy is that it is possible to answer an exponential number of such queries on a dataset [8, 25, 20].”
Private Query Release Assisted by Public Data (2020, background): “This question has been extensively studied in the literature on differential privacy (Dinur & Nissim, 2003; Hardt & Rothblum, 2010; Muthukrishnan & Nikolov, 2012; Blum et al., 2013; Bun et al., 2018; Steinke & Ullman, 2015).”
The Large Margin Mechanism for Differentially Private Maximization (2014, background): “Lower bounds for approximate differential privacy have been shown by [7, 16, 11, 9], and the proof of our Theorem 1 borrows some techniques from [11].”