Differentially Private Release and Learning of Threshold Functions

Mark Bun, Kobbi Nissim, Uri Stemmer +1

We prove new upper and lower bounds on the sample complexity of $(\hat{I}\mu ,\hat{I}´)$ differentially private algorithms for releasing approximate answers to threshold functions. A threshold f…