PhD Course - The Complexity of Differential Privacy

Title:

The Complexity of Differential Privacy

Organizers:

Martin Aumüller, Christian Janos Lebeda

Lecturers:

Each session one participant is responsible for presenting the covered topic and leading the discussion. Each participant must present at least once during the course to earn credits.

Dates of the course:

Joint sessions: October 5 2021 to December 21 2021.

Project deadline: February 1 2022.

Time:

Tuesday from 10:00 to 11:00.

Room:

Hybrid – Zoom and Auditorium 4 at ITU

Course description:

The course consists of 11 joint sessions and a project phase.

During each 1-hour session, a participant will present part of The Complexity of Differential Privacy by Salil Vadhan. The presentation should last 20-30 minutes. The remaining time is used for joint discussion of the covered material. The final two sessions are reserved for discussing interesting research papers/ideas.  The exact topics will be determined during the course.

The goal of this course is to give the participants an overview of differential privacy as well as some of the connections to other topics in theoretical computer science. Every participant should read the covered material before the session. The projects will be based on a research paper not covered during the joint sessions.

Reading list:

• The Complexity of Differential Privacy by Salil Vadhan.
• Relevant research papers.

Programme:

05/10/2021 – Chapter 1 & 2: Introduction and Definition & Composition Theorems for Differential
Privacy
12/10/2021 – Chapter 3: Alternative to Global Sensitivity
19/10/2021 – Fall break
26/10/2021 – Chapter 4: Releasing Many Counting Queries with Correlated Noise
02/11/2021 – Chapter 5: Information-Theoretical Lower Bounds
09/11/2021 – Chapter 6: Computational Lower Bounds
16/11/2021 – Chapter 7: Efficient Algorithms for Specific Query Families
23/11/2021 – Chapter 8: Private PAC Learning
30/11/2021 – Chapter 9: Multiparty Differential Privacy
07/12/2021 – Chapter 10: Computational Differential Privacy
14/12/2021 – TBD: Relevant research paper(s)
21/12/2021 – TBD: Relevant research paper(s)
01/02/2022 – Project deadline

Prerequisites:

Knowledge of algorithms and basic probability theory. The first session is an introduction to the
topic.

Exam:

Each student must present at least once during the course.
At the end of the course the student must hand in a project report. Martin Aumüller will evaluate
the report.

Credits:

5 ECTS

Amount of hours the student is expected to use on the course:

Participation: 11 hours
Preparation (reading/prepare presentation): 60 hours
Project work: 60 hours
Total: 131 hours

Participants:

The course is targeting PhD students and other researchers interested in differential privacy. Maximum 9 participating PhD students

How to sign up:

Contact Christian Janos Lebeda at chle@itu.dk