Between Pure and Approximate Differential Privacy

Thomas Steinke, Jonathan Ullman

We show a new lower bound on the sample complexity of $(\epsilon ,\delta )$-differentially private algorithms that accurately answer statistical queries on high-dimensional databases.…