קולוקוויום בביה"ס למדעי המחשב - Locally Private Heavy-Hitters

Abstract:

In the heavy-hitters problem, each user has an input item, and our goal is to identify all "heavy-hitters", which are common input items.  We study the heavy-hitters problem in the local model of differential privacy (LDP), where the users randomize their data locally, and only send noisy reports to an untrusted server that aggregates them. 

The heavy-hitters problem is perhaps the most well-studied problem in local differential privacy. In practice, LDP algorithms for heavy-hitters have already been implemented and used at scale. Two prominent examples are by Google in the Chrome browser and Apple in iOS-10, making LDP heavy-hitters the most widespread industrial application of differential privacy to date.

We present new heavy-hitters algorithms satisfying LDP, with optimal or near-optimal worst-case error, running time, and memory. 

Based on a joint work with Raef Bassily, Kobbi Nissim, and Abhradeep Thakurta, and a joint work with Mark Bun and Jelani Nelson.