CS7880: Rigorous Approaches to Data Privacy
Time & Location:
1:35 - 3:15pm TF, Ryder Hall 157
Staff
Instructor: Jonathan Ullman
Office: 260 West Village H
Office Hours: 1:00-2:00pm W
Updates
Overview
How can we enable the analysis of datasets with sensitive information about individuals while protecting the privacy of those individuals? Over the past decade, a new line of work in theoretical computer science—differential privacy—has provided a framework for computing on sensitive datasets in which one can mathematically prove that individual-specific information does not leak. Many useful data analysis tasks can be accomplished while satisfying the strong privacy requirement of differential privacy, and differential privacy is starting to have significant impact on practice. This line of work has also shown that differential privacy is connected to many other areas, both inside theoretical computer science (learning theory, cryptography, complexity theory, convex geometry, mechanism design, etc.) and outside (databases, programming languages, security, statistics, law, policy, etc.)
This course will cover the theory of differential privacy, its application, and its connections to other areas of computer science, covering roughly the state-of-the-art in the field. Topics include (but are not limited to):
- Defining differential privacy --- composition, post-processing, robustness
- Basic algorithms --- laplace, gaussian, and exponential mechanisms
- Beyond the worst-case --- global/local/smooth/restricted sensitivity and PTR
- Advanced algorithms --- query Release, marginal tables
- The limits of privacy --- packing, reconstruction attacks, tracing attacks
- Computational hardness results
- Differentially private learning --- PAC Learning, SQ Learning, convex optimization
- Differential privacy and generalization in learning
- Additional topics depending on time and students' interests. Potentially:
- Connections to high-dimensional geometry
- Graph analysis
- Privacy and mechanism design
- Distributed differential privacy --- local model and secure computation
- Programming languages and formal verification for differential privacy
- Etc.
Prerequisites
Mathematical maturity, and some experience with probability and randomized algorithms. Algorithms (CS7800 or equivalent) is preferred. Students in areas other than theory are welcome! If you are interested in the course, but uncertain about your background, please come and talk to me!
Textbooks
Most of the reading will come from the excellent textbook
The Algorithmic Foundations of Differential Privacy by Cynthia Dwork and Aaron Roth. There will also be assigned readings from Salil Vadhan's fantastic survey
The Complexity of Differential Privacy. Later on in the course I will be reading from original research papers.
NB
We will be using
NB for course readings. PDFs of the assigned reading will appear on NB, and you will be expected to post comments or questions about the reading, or address other students' questions and comments. Participation on NB (both frequency and quality) will make up a small portion of your final grade.
Use this link to sign up for NB.
Grading
The primary output for this course will be a final project on a (suitable) topic of your choosing. There will be no exams. The rest of the grade will be based on 2-3 problem sets early in the semester to test understanding of key concepts, and participation in class and on NB. The final grade will be broken down roughly into: