Fingerprinting Codes and the Price of Approximate Differential Privacy

Mark Bun, Jonathan Ullman, Salil Vadhan

We show new lower bounds on the sample complexity of $(\epsilon ,\delta )$-differentially private algorithms that accurately answer large sets of counting queries. A counting query on…