Seminar on Differential Privacy

Iftach Haitner and Nikolaos Makriyannis

Tuesdays: 10:00-12:00, Room: Dan David 204

Differential Privacy is an exciting mathematically rigorous definition of data privacy. After defining the notion, we will  motivate and discuss the meaning of this definition,  and learn the fundamental techniques for achieving it.  In most parts, the seminar will follow the The Algorithmic Foundations of Differential Privacy monograph by Cynthia Dwork and Aaron Roth.

In each meeting one student will cover a single topic as listed below.

Talks are to be given in English.


This is an advanced seminar, so background in the theory of computation (Algorithm, Computability, Complexity) is required. Students with particularly strong math background are also welcome.

Undergrad students

Third year students who are willing to work hard, are welcome to join the seminar, but please consult me via email before registering.


Power Point presentations are acceptable, but white boards ones are preferable.
To do a good job one needs to read background material (see the reading section).
In addition, the speakers of the week will have to give me a practice talk a week before (right after the talk of that week).

Topics and schedule

Will be published before before spring semester starts (see additional reading for further reading on your lecture topic).

# When Who What
1 06/03 Nikolaos Makriyannis
2 13/03 Oded Nir
Basic techniques (part 1)

Chapter 3.1 to 3.5
Relevant talks: [video1] [video2]
3 20/03 Or Almer
Basic techniques (part 2)

Chapter 3.6
Relevant talks: [video]
4 10/04 Inbar Oren
BLR mechanism and Generalization

Chapters 4.1 & 5.1
5 17/04 Michael Bargury
Private multiplicative weights - PMW

Chapter 4.2
Relevant talks: [video]
6 24/04 Itai Admi
Iterative construction mechanism (generalization of PMW)

Chapter 5.2
01/05 NO CLASS
7 08/05 Nir Eshdat
Boosting for queries algorithm

Chapter 6.1
8 15/05 Amit Zohar
Exploiting low local sensitivity

Chapters 7.1 & 7.2
Relevant talks: [video]
9 22/05 Shlomi Shamir
Reconstruction attacks

Chapter 8.1
Relevant talks: [video]
10 29/05 Daniel Katzman
Lower bounds by packing arguments

Chapter 8.2
Relevant talks: [video]
11 05/06 Matan Orland
Limits of poly-time curators

Chapters 9.1 & 9.2
12 12/06 Bar Alon
Traitor tracing and ramifications to DP

Chapter 9.2.1 and Sections 3 & 4 in this paper
Relevant talks: [video]

Additional material