  We consider the problem of answering $k$ counting (i.e. sensitivity-1)
queries about a database with $(\epsilon, \delta)$-differential privacy. We
give a mechanism such that if the true answers to the queries are the vector
$d$, the mechanism outputs answers $\tilde{d}$ with the $\ell_\infty$-error
guarantee:
  $$\mathcal{E}\left[||\tilde{d} - d||_\infty\right] = O\left(\frac{\sqrt{k
\log \log \log k \log(1/\delta)}}{\epsilon}\right).$$
  This reduces the multiplicative gap between the best known upper and lower
bounds on $\ell_\infty$-error from $O(\sqrt{\log \log k})$ to $O(\sqrt{\log
\log \log k})$. Our main technical contribution is an analysis of the family of
mechanisms of the following form for answering counting queries: Sample $x$
from a \textit{Generalized Gaussian}, i.e. with probability proportional to
$\exp(-(||x||_p/\sigma)^p)$, and output $\tilde{d} = d + x$. This family of
mechanisms offers a tradeoff between $\ell_1$ and $\ell_\infty$-error
guarantees and may be of independent interest. For $p = O(\log \log k)$, this
mechanism already matches the previous best known $\ell_\infty$-error bound. We
arrive at our main result by composing this mechanism for $p = O(\log \log \log
k)$ with the sparse vector mechanism, generalizing a technique of Steinke and
Ullman.
