The Algorithmic Foundations of Data Privacy
CSCI 8980
Fall 2018

Suggested papers for reading projects.

Attacks on Privacy:

[NS06]: Narayanan and Shmatikov,
Robust De-anonymization of Large Datasets: How to Break Anonymity of the Netflix Prize Dataset.
[CKNFS11]: Calandrino et al.,
“You Might Also Like:” Privacy Risks of Collaborative Filtering.
[Korolova11]: Korolova et al.,
Privacy Violations Using Microtargeted Ads: A Case Study.
[CCPS15]: Conti et al.,
TRAP: using TaRgeted Ads to unveil Google personal Profiles.
[SSSS17]: Shokri et al.,
Membership Inference Attacks Against Machine Learning Models.

Early papers: definitions, basic mechanisms, properties

[DN03]: Dinur, Nissim,
Revealing Information while Preserving Privacy.
[DMNS06]: Dwork, McSherry, Nissim, Smith,
Calibrating Noise to Sensitivity in Private Data Analysis.
[DKMMN06]: Dwork, Kenthapadi, McSherry, Mironov, Noar,
Our Data, Ourselves: Privacy via Distributed Noise Generation.

More tools and algorithmic techniques

[MT07]: McSherry, Talwar,
Mechanism Design via Differential Privacy.
[NRS07]: Nissim, Raskhodnikova, Smith,
Smooth Sensitivity and Sampling in Private Data Analysis.
[DL09]: Dwork, Lei,
Differential Privacy and Robust Statistics.
[RR10]: Roth, Roughgarden,
Interactive Privacy via the Median Mechanism.
[HR10]: Hardt, Rothblum,
A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis.
[DRV10]: Dwork, Rothblum, Vadhan,
Boosting and Differential Privacy.
[NTZ12]: Nikolov, Talwar, Zhang,
The Geometry of Differential Privacy: The Sparse and Approximate Cases.
[ST13]: Smith, Thakurta,
Differentially Private Model Selection via Stability Arguments and the Robustness of the Lasso.

Differentially private machine learning

[KLNRS08]: Kasiviswanathan, Lee, Nissim, Raskhodnikova, Smith,
What can we learn privately?
[CMS11]: Chaudhuri, Monteleoni, Sarwate,
Differentially private empirical risk minimization.
[BKN13]: Beimel, Kasiviswanathan, Nissim,
Bounds on the Sample Complexity for Private Learning and Private Data Release.
[BNS13]: Beimel, Nissim, Stemmer,
Characterizing the Sample Complexity of Private Learners.
[ST13]: Smith, Thakurta,
Differentially Private Model Selection via Stability Arguments and the Robustness of the Lasso.
[BST14]: Bassily, Smith, Thakurta,
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds.
[BNSV15]: Bun, Nissim, Stemmer, Vadhan,
Differentially Private Release and Learning of Threshold Functions.
[SS15]: Shokri, Shmatikov,
Privacy-Preserving Deep Learning.
[ACG+16]: Papernot, Abadi, Erlingsson, Goodfellow, McMahan, Mironov, Talwar, Zhang.
Deep Learning with Differential Privacy.
[PAEGT17]: Papernot, Abadi, Erlingsson, Goodfellow, Talwar,
Semi-Supervised Knowledge Transfer for Deep Learning from Private Training Data.
[BTT18]: Bassily, Thakkar, Thakurta,
Model-Agnostic Private Learning.

Local (Distributed) Model of Differential Privacy

[HKR12]: Hsu, Khanna, Roth,
Distributed Private Heavy Hitters.
[DJW13]: Duchi, Jordan, Wainwright,
Local Privacy, Data Processing Inequalities, and Minimax Rates.
[EKP14]: Erlingsson, Korolova, Pihur,
RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response.
[BS15]: Bassily, Smith,
Local, Private, Efficient Protocols for Succinct Histograms.
[BNST17]: Bassily, Nissim, Stemmer, Thakurta,
Practical Locally Private Heavy Hitters.

Differential Privacy for Streaming

[DNPR10]: Dwork, Naor, Pitassi, Rothblum,
Differential Privacy Under Continual Observation.
[CSS11]: Chan, Shi, Song,
Private and Continual Release of Statistics.

Lower Bounds (Limits of Differential Privacy)

[HT10]: Hardt, Talwar,
On the Geometry of Differential Privacy.
[De11]: De,
Lower bounds in differential privacy.
[BUV14]: Bun, Ullman, Vadhan,
Fingerprinting Codes and the Price of Approximate Differential Privacy.
[BST14]: Bassily, Smith, Thakurta,
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds.

Relaxations of Differential Privacy

[BBGLT12]: Bhaskar et al.,
Noiseless Database Privacy.
[KM12]: Kifer, Machanavajjhala,
A Rigorous and Customizable Framework for Privacy.
[BGKS13]: Bassily, Groce, Katz, Smith,
Coupled-Worlds Privacy: Exploiting Adversarial Uncertainty in Statistical Data Privacy.
[BF16]: Bassily, Freund,
Typical Stability.

Differential Privacy for Robust Adaptive Data Analysis

[DFHPRR15-a]: Dwork, Feldman, Hardt, Pitassi, Reingold, Roth,
Preserving Statistical Validity in Adaptive Data Analysis.
[BNSSSU16]: Bassily, Nissim, Smith, Steinke, Stemmer, Ullman,
Algorithmic Stability for Adaptive Data Analysis.
[DFHPRR15-b]: Dwork, Feldman, Hardt, Pitassi, Reingold, Roth,
Generalization in Adaptive Data Analysis and Holdout Reuse.
[CLNRW16]: Cummings, Ligett, Nissim, Roth, Wu,
Adaptive Learning with Robust Generalization Guarantees.
[RRST16]: Rogers, Roth, Smith, Thakkar,
Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing.
[FS17-a]: Feldman, Steinke,
Generalization for Adaptively-chosen Estimators via Stable Median.
[FS17-b]: Feldman, Steinke,
Calibrating Noise to Variance in Adaptive Data Analysis.