Instructor: Rachel Cummings
Office: Mudd 535E
Prerequisites: Undergraduate-level courses on probability, algorithms, and proof-based mathematics. Instructor’s permission required for undergraduate and Master’s students.
Description: How should we define privacy? How can we enable the analysis of data containing sensitive information about individuals while protecting the privacy of those individuals? What are the tradeoffs between useful analyses of large datasets, and the privacy of the individuals from whom the data are derived? This course will take a mathematically rigorous approach to addressing these and other questions at the foundations of research in data privacy. This course will take a mathematically rigorous approach to addressing these and other questions at the foundations of research in data privacy. We will draw connections to a wide variety of topics, including economics, statistics, optimization, learning theory, information theory, and approximation algorithms.
Schedule and Course notes:
Schedule subject to change. Check back regularly for updates.
| Date | Topic | Reading | Assignment |
| Lect 1 | DP definition, Laplace Mech, Rand Resp | Ch 1 – 3.3 | |
| Lect 2 | Exponential mech, DP properties | Ch 3.4 | HW 1 due |
| Lect 3 | Sparse Vector | Ch 3.5, 3.6 | |
| Lect 4 | SmallDB | Ch 4.1 | HW 2 due |
| Lect 5 | Private Multiplicative Weights | Ch 4.2 | |
| Lect 6 | DP-ERM | Chaudhuri et al. | HW 3 due | Lect 7 | Continual observation/release | Ch 12.3 | Proposal due |
| Lect 8 | DP and mechanism design | Ch 10 | |
| Lect 9 | DP and deep learning | Abadi et al. | |
| Lect 10 | Local privacy and Heavy Hitters | Bassily and Smith | |
| Lect 11 | Student presentations | ||
| Not covered | Beyond Worst-case | Ch 7.1, 7.2 | |
| Not covered | Federated Private Heavy Hitters | Zhu et al., Kairouz et al. | |
| Not covered | Privacy and Fairness | Cummings | |
| Final exams (no class) | Project due |
Courseworks: Class announcements, assignments, and updates will be posted on Courseworks.
Textbook: The Algorithmic Foundations of Differential Privacy by Cynthia Dwork and Aaron Roth. The pdf version is available for free; the paper version is on Amazon for $99. We will also be reading research papers, which will be posted on the course website throughout the semester.
Grading: The main graded components of the course are as follows:
- 3 Homework assignments (10% each)
- Participation and engagement (25%)
- Final project (45%)
This breakdown may change during the term, particularly as enrollment levels settle.
Final project: You will be expected to do a final project on a topic of your choosing, either individually or in small groups. Your project should provide good opportunities to connect the course material to your other interests and get some exposure to doing original research in differential privacy. This will involve submitting a detailed project proposal for feedback, completing the proposed project, producing a written paper, and presenting your project in class at the end of the semester. More details will be posted early in the course about project requirements and suggested topics.
Resources from similar courses: This course’s design, content, and website are based in part on similar courses:
- Introduction to Data Privacy, taught by Katrina Ligett at Caltech.
- The Algorithmic Foundations of Data Privacy, taught by Aaron Roth at UPenn.
- Algorithmic Challenges in Data Privacy, taught by Sofya Raskhodnikova and Adam Smith at Penn State.
- Foundations of Privacy, taught by Moni Naor, at the Weizmann Institute.
- Mathematical Approaches to Data Privacy, taught by Salil Vadhan at Harvard.