CSE 598A Algorithmic Challenges in Data Privacy
Spring 2010

Welcome to the course web page for CSE 598A!

Course Staff

Office Phone Email @psu.edu Office Hours
Prof. Sofya Raskhodnikova IST 343F x3-0608 sofya@cseTue. 3:45pm-4:45pm
Prof. Adam D. Smith IST 338K x3-0076 asmith+598 Thu. 3:45pm-4:45pm


Lec Date Topics Reading Announcement
1 Jan 14 Introduction to Class, Chebyshev Inequality, Sampling for Estimating Average
2 Jan 19 k-Anonymity, Composition Attacks, Differential Privacy GKS08
3 Jan 21 Examples of Differentially Private Algorithms, Properties of Differential Privacy, Global Sensitivity Framework DMNS06
4 Jan 26 Global Sensitivity Examples: Mean and Covariance
Properties of Differential Privacy: Composition and Post-Processing
5 Jan 28 Perceptron Algorithm, Noisy Perceptron BDMN05 Novikoff62 HW 1 out
due Feb 9
6 Feb 2 Post-Processing, Consistency, Histograms, Noise Characterization and Noise Reduction BCDKMT07 HRMS10
7 Feb 4 Smooth Sensitivity: Example of Median Finding NRS08
8 Feb 9 Dinur-Nissim Attack DN03
9 Feb 11 Smooth Sensitivity: Minimum Spanning Tree NRS08
10 Feb 16 Exponential Mechanism MT08
11 Feb 18 Introduction to Computational Learning KV94 KLNRS08
12 Mar 2 Differentially Private Learning KLNRS08
13 Mar 4 Non-Interactive Database Privacy BLR08 HW 2 out
due Mar 18
14 Mar 16 Dwork-Yekhanin Attack DY08
15 Mar 18 Dwork-McSherry-Talwar Attack DMT07
16 Mar 23 Review of Reconstruction Algorithms KRSU10
17 Mar 25 Lower Bounds Specific to Differential Privacy and its Variants HT10
18 Mar 30 Differentially Private Combinatorial Optimization: k-Median GLMRT10
19 Apr 1 Differentially Private Combinatorial Optimization: Vertex Cover GLMRT10
20 Apr 6 Smooth Sensitivity: Clustering NRS08
21 Apr 8 Sample-and-Aggregate NRS08
22 Apr 13 Continual Observations and Differential Privacy DNPR10
23 Apr 15 Non-Interactive Database Privacy: Efficient Version DNRRV09
24 Apr 20 Differentially-Private Convex Optimization CM08
25 Apr 22 Differentially-Private L2 Regularized Linear Regression CM08
26 Apr 27 Student Presentation: Fang / Madhav, Ramesh / Abhradeep
27 Apr 29 Student Presentation: Bin-Rong, Zhi, and Youngtae


GKS08 Srivatsava Ranjit Ganta, Shiva Prasad Kasiviswanathan and Adam Smith Composition Attacks and Auxiliary Information in Data Privacy KDD 2008
DMNS06 Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith Calibrating Noise to Sensitivity in Private Data Analysis TCC 2006.
BDMN05 Avrim Blum, Cynthia Dwork, Frank McSherry and Kobbi Nissim Practical Privacy: the SuLQ framework PODS 2005
Novikoff62 A.B. Novikoff, On Convergence Proofs on Perceptrons, Proceedings of the Symposium on the Mathematical Theory of Automata 1962
BCDKMT07 Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry and Kunal Talwar Privacy, Accuracy, and Consistency too: A Holistic solution to Contingency Table Release in PODS 2007.
HRMS10 Michael Hay, Vibhor Rastogi, Gerome Miklau and Dan Suciu Boosting the Accuracy of Differentially Private Histograms through Consistency
NRS08 Kobbi Nissim, Sofya Raskhodnikova and Adam Smith Smooth Sensitivity and Sampling in Private Data Analysis STOC 07
DN03 Irit Dinur and Kobbi Nissim Revealing Information while Preserving Privacy PODS 2003
MT08 Frank McSherry and Kunal Talwar Mechanism Design via Differential Privacy FOCS 2007
KV94 Michael Kearns and Umesh Vazirani An Introduction to Computational Learning Theory MIT Press 1994.
The e-book is viewable only from university IP addresses.
KLNRS08 Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova and Adam Smith What Can We Learn Privately? FOCS 2008
BLR08 Avrim Blum, Katrina Ligett and Aaron Roth A Learning Theory Approach to Non-Interactive Database Privacy STOC 2008
DY08 Cynthia Dwork and Sergey Yekhanin New Efficient Attacks on Statistical Disclosure Control Mechanisms CRYPTO 2008
DMT07 Cynthia Dwork, Frank McSherry, and Kunal Talwar The Price of Privacy and the Limits of LP Decoding STOC 2007
KRSU10 Shiva Kasiviswanathan, Mark Rudelson, Adam Smith and Jonathan Ullman The Price of Privately Releasing Contingency Tables and the Spectra of Random Matrices with Correlated Rows to appear at STOC 2010
HT10 Moritz Hardt and Kunal Talwar On the Geometry of Differential Privacy to appear at STOC 2010
GLMRT10 Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar Differentially Private Approximation Algorithms SODA 2010
DNPR10 Cynthia Dwork, Moni Naor, Toni Pitassi and Guy Rothblum, Differential Privacy Under Continual Observation, to appear at STOC 2010
Powerpoint is available at IPAM workshop and video lecture is availabe at IAS
DNRRV09 Cynthia Dwork, Moni Naor, Omer Reingold, Guy Rothblum and Salil Vadhan On the Complexity of Differentially Private Data Release: Efficient Algorithms and Hardness Results STOC 2009
CM08 Kamalika Chaudhuri and Claire Monteleoni Privacy-Preserving Logistic Regression NIPS 2008


For tips on using latex to type homework, see these links.
Other Useful Programs
On Mac, emacs and Skim

Last modified: Sat Apr 24 15:51:47 EDT 2010