CSE 711 - Spring 2016 - Topics in Differential Privacy

Location: Davis 113A
Time: Thursday 10:30 - 12:00
Instructor: Marco Gaboardi
e-mail: gaboardi@buffalo.edu

Credits: 3
Office Hours: Thursday 12:00 - 1:00 or by appointment
Discussion forums: NB and Piazza (by invitation)


This will be a graduate level seminar-style course introducing differential privacy and some of its applications. Differential privacy is a promising approach to the privacy-preserving release of data: it offers a strong guaranteed bound on the increase in harm that a user incurs as a result of participating in a differentially private data analysis. Several mechanisms and software tools have been developed to ensure differential privacy for a wide range of data analysis tasks, such as combinatorial optimization, machine learning, answering distributed queries, etc. In this class we will focus on some fundamental results about the theory and practice of differential privacy and how to use it in concrete applications. Part of the course will also focus on the use of differential privacy for purposes different from protecting privacy like for instance as a technique to prevent false discoveries in experimental science. The course will consist of readings on advanced topics in differential privacy and applications from the programming language, algorithmic, database, machine learning, security, and systems perspective.

Course description

The course is offered as 1, 2 or 3 credits. This will be seminar-style course where each student will select and present an article from the literature on differential privacy and applications. Students are expected to read and comment the presented papers previous to class by using NB. Every student will also be invited to engage on one project and to present the results at the end of the course. Discussion about all the aspects of the course will also take place on Piazza.


The grading will be based on the presentation of one paper, participation in class and in the NB and Piazza discussions, and a final project. Students who are not interested in a project can instead present a second article.
The final grade will be composed as:

  • 30% Presentation of an article in class,
  • 40% Engagement and participation in class, on NB, and on Piazza,
  • 30% Project presentation or another article presentation.
  • Projects

    Projects can take different forms depending on the interest of each student but all the project must have a research component. Some examples of what would constitute a good project are:

  • design of a new differentially private algorithm for a specific task
  • design or implementation of (part of) a new programming language, system, or tool for differential privacy
  • implementation of a previously published work and an experimental comparison with other works with similar targets,
  • investigate new applications of differential privacy

  • The instructor will provide some specific ideas for possible projects after the first class but other ideas may be accepted if well motivated and discussed with the instructor. Students may work on their projects alone or they may collaborate with others. Groups can be composed by at most two students. Each group is invited to meet with the instructor regularly (3-4 times during the term) to check on the advancements and directions of the project.


    Date Topic Presenter
    1/28 Introduction to Differential Privacy - basic definitions and mechanisms
    Optional reading: Chapter 1 and 2 of The Algorithmic Foundations of Differential Privacy, Dwork and Roth, 2014.
    Marco Gaboardi
    Class introduction
    2/04 Continuing the Introduction to Differential Privacy - basic definitions and mechanisms Marco Gaboardi
    2/11 Frank McSherry, Privacy Integrated Queries. SIGMOD09. Akash Mandole
    Daniel Kifer and Ashwin Machanavajjhala, No free lunch in data privacy. SIGMOD11. Syed Mohammed Arshad Zaidi
    2/18 Cynthia Dwork, Guy N. Rothblum, Salil P. Vadhan, Boosting and Differential Privacy. FOCS10. Swapnil Sudam Auti
    Zuhe Zhang, Benjamin Rubinstein, Christos Dimitrakakis, On the differential privacy of Bayesian Inference. AAAI16. Gian Pietro Farina
    2/25 Prashanth Mohan, Abhradeep Thakurta, Elaine Shi, Dawn Song, David E. Culler, GUPT: privacy preserving data analysis made easy. SIGMOD12. Namita Marathe
    Kamalika Chaudhuri, Daniel Hsu, Shuang Song, The Large Margin Mechanism for Differentially Private Maximization. NIPS14. Shubham Sharma
    3/3 Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum, Differential privacy under continual observation. STOC10. Keval Bhavesh Goradia
    Moritz Hardt, Katrina Ligett, Frank McSherry, A Simple and Practical Algorithm for Differentially Private Data Release. NIPS12. Alizishaan Anwar Hussein Khatri
    3/10 Arjun Narayan, Ariel Feldman, Antonis Papadimitriou, Andreas Haeberlen, Verifiable differential privacy. Eurosys15. Pranav Pramod Gadekar
    Konstantinos Chatzikokolakis, Catuscia Palamidessi, Marco Stronati: Geo-indistinguishability: A Principled Approach to Location Privacy. ICDCIT15 Dhaval Taunk
    3/17 No class - Spring Break
    3/24 Florian Tramer, Zhicong Huang, Jean-Pierre Hubaux, Erman Ayday: Differential Privacy with Bounded Priors: Reconciling Utility and Privacy in Genome-Wide Association Studies. CCS15 Nalin Kumar
    Frank McSherry, Kunal Talwar: Mechanism Design via Differential Privacy. FOCS07 Arti Gupta
    3/31 No class
    4/7 Michael Hay, Ashwin Machanavajjhala, Gerome Miklau, Yan Chen, and Dan Zhang: Principled Evaluation of Differentially Private Algorithms using DPBench. SIGMOD16 Kapil Sharma
    Myrto Arapinis, Diego Figueira, Marco Gaboardi: Sensitivity of Counting Queries. Draft Desmond Pinto
    4/14 Yevgeniy Dodis, Adriana López-Alt, Ilya Mironov, Salil P. Vadhan: Differential Privacy with Imperfect Randomness. CRYPTO 2012: 497-516 Pranav Pramod Gadekar - Namita Balkrishna Marathe
    Daniel Kifer and Ashwin Machanavajjhala. A Rigorous and Customizable Framework for Privacy. PODS 2012. Syed Mohammed Arshad Zaidi
    4/21 Kamalika Chaudhuri, Staal Vinterbo: Stability-based Validation Procedure for Differentially Private Machine Learning. NIPS 2013. Swapnil Sudam Auti - Kapil Sharma
    Jason Reed, Benjamin C. Pierce: Distance makes the types grow stronger: a calculus for differential privacy. ICFP 2010: 157-168 Gian Pietro Farina
    4/28 Cyrus Shahabi, Liyue Fan, Luciano Nocera, Li Xiong and Ming Li. Privacy-Preserving Inference of Social Relationships from Location Data: A Vision Paper, ACM SIGSPATIAL, 2015 Akash Mandole - Nalin Kumar
    Peter Kairouz, Sewoong Oh, Pramod Viswanath: Secure Multi-party Differential Privacy, NIPS 2015 Shubham Sharma
    5/5 Samuel Haney, Ashwin Machanavajjhala, Bolin Ding: Secure Design of Policy-Aware Differentially Private Algorithms, PVLDB 2015 Arti Gupta
    Georgios Kellaris, Stavros Papadopoulos, Xiaokui Xiao, Dimitris Papadias: Differentially Private Event Sequences over Infinite Streams. PVLDB 7(12): 1155-1166 (2014) Keval Bhavesh Goradia
    Project Presentation Dhaval Taunk - Desmond Pinto
    Project Presentation Alizishaan Anwar Hussein Khatri