Seminar on differential privacy, Fall 19/20

Haim Kaplan


Please pick three options for your lecture, rank them, and send them to me asap. The first four lectures (2-5) are on basic techniques to build DP mechanisms. Lectures (6-7) are on how to answer many queries by sharing the randomness we use for these answers. Lecture 8 touches techniques to reduce the sensitivity of sensitive functions so we can privatize them. Lectures 9-11 cover lower bounds (information theoretic and computational). Lecture 12-13 study interesting issues related to privacy and machine learning.

We will go over the fundamental techniques for designing differentially private algorithms and techniques for proving lower bounds on the complexity of such algorithms. In the last part of the seminar we will focus mainly on differentially private machine learning algorithms. We will use the two monographs:

       C. Dwork and A. Roth, The algorithmic foundations of differential privacy, 2014 (I will refer to this book as DW below)

       S. Vadhan, The complexity of differential privacy, 2017,

and some additional paper. Lectures may depend on previous ones so it is strongly recommended that you follow the material closely and read ahead using these books.

I would like to meet each one of you at least a week before your lecture (I recommend you do it as early as possible in case we need more than one meeting or there are some difficult proofs to understand). We will go over your planned lecture and your slides/notes.

I suggest you start reading your material as soon as possible, I am available for any question you may have, either regarding the technical material or regarding planning the parts you will deliver and how.


1)    (Oct 30) An introductory lecture

2)    (Nov 6) The Laplace and Gaussian mechanisms, 3.3 and appendix A in DR, Gal Sadeh

3)    (Nov 13) The exponential mechanism and how to answer linearly many queries (SMALLDB), 3.4 and 4.1 in DR, original texts: McSherry and K.Talwar. Mechanism Design via Differential Privacy, FOCS 2007, and Blum, Ligett, and Roth, A Learning Theory Approach to Differential Privacy, J. ACM 60(2): 2013, Benjamin Doubior

4)    (Nov 20) Composition theorem for differential privacy, 3.5 and appendix B in DR, original texts: C. Dwork and J. Lei, Differential Privacy and Robust Statistics STOC 2009, and C. Dwork, G. N. Rothblum, and S. P. Vadhan. Boosting and differential privacy FOCS 2010, Amir Hertz

5)    (Nov 27) The sparse vector technique, 3.6 in DR, additional text: Lyu, Su and Li, Understanding the Sparse Vector Technique for Differential Privacy. PVLDB 10(6): 637-648 (2017), Roni Yasinnik

6)    (Dec 4) Online query release via private multiplicative weights, 4.2 in DR, original text: Hardt and Rothblum: A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis, FOCS 2010, Omri Keren

7)    (Dec 11) Offline generalizations of the multiplicative weights algorithm, 5.2,5.3 in DR and look also at the references there, Saeed Esmail

8)    (Dec 18) When worst case sensitivity is atypical, Chapter 7 in DR, original text: Smith and Thakurta, Differentially Private Feature Selection via Stability Arguments and the Robustness of the Lasso, COLT 2013, Ori Terner

9)    (Dec 25) Lower bounds for differential privacy, Chapter 8 in DR and the references there, Gefen Keinan

10) (Jan 1) Lower bounds using fingerprinting codes, Section 5.3 in the book of Vadhan, original text: Bun, Ullman, and Vadhan, Fingerprinting Codes and the Price of Approximate Differential Privacy, SIAM J. Comput., 47(5) 2018

11) (Jan 8) Differential privacy and computational complexity, Chapter 9 in DR, Section 6 in Vadhan

12) (Jan 15) Kasiviswanathan, Lee, Nissim, Raskhodnikova, and Smith, What Can We Learn Privately, SIAM J. Comput., 40(3) 2011, Or Shahaf

13) (Jan 22) Beimel, Brenner, Kasiviswanathan and Nissim, Bounds on the sample complexity for private learning and private data release, Machine Learning 94(3) 2014, Abed Khateeb