Oneshot Differentially Private Top-k Selection
  Being able to efficiently and accurately select the top-$k$ elements with
differential privacy is an integral component of various private data analysis
tasks. In this paper, we present the oneshot Laplace mechanism, which
generalizes the well-known Report Noisy Max mechanism to reporting noisy
top-$k$ elements. We show that the oneshot Laplace mechanism with a noise level
of $\widetilde{O}(\sqrt{k}/\eps)$ is approximately differentially private.
Compared to the previous peeling approach of running Report Noisy Max $k$
times, the oneshot Laplace mechanism only adds noises and computes the top $k$
elements once, hence much more efficient for large $k$. In addition, our proof
of privacy relies on a novel coupling technique that bypasses the use of
composition theorems. Finally, we present a novel application of efficient
top-$k$ selection in the classical problem of ranking from pairwise
comparisons.
