Between Pure and Approximate Differential Privacy
  We show a new lower bound on the sample complexity of $(\varepsilon,
\delta)$-differentially private algorithms that accurately answer statistical
queries on high-dimensional databases. The novelty of our bound is that it
depends optimally on the parameter $\delta$, which loosely corresponds to the
probability that the algorithm fails to be private, and is the first to
smoothly interpolate between approximate differential privacy ($\delta > 0$)
and pure differential privacy ($\delta = 0$).
  Specifically, we consider a database $D \in \{\pm1\}^{n \times d}$ and its
\emph{one-way marginals}, which are the $d$ queries of the form "What fraction
of individual records have the $i$-th bit set to $+1$?" We show that in order
to answer all of these queries to within error $\pm \alpha$ (on average) while
satisfying $(\varepsilon, \delta)$-differential privacy, it is necessary that
$$ n \geq \Omega\left( \frac{\sqrt{d \log(1/\delta)}}{\alpha \varepsilon}
\right), $$ which is optimal up to constant factors. To prove our lower bound,
we build on the connection between \emph{fingerprinting codes} and lower bounds
in differential privacy (Bun, Ullman, and Vadhan, STOC'14).
  In addition to our lower bound, we give new purely and approximately
differentially private algorithms for answering arbitrary statistical queries
that improve on the sample complexity of the standard Laplace and Gaussian
mechanisms for achieving worst-case accuracy guarantees by a logarithmic
factor.
