Tight Data Access Bounds for Private Top-$k$ Selection

Hao Wu, Olga Ohrimenko, Anthony Wirth

We study the top-$k$ selection problem under the differential privacy model: $m$ items are rated according to votes of a set of clients. We consider a setting in which algorithms c…