Timezone: »

 
Oral
Differentially Private Clustering: Tight Approximation Ratios
Badih Ghazi · Ravi Kumar · Pasin Manurangsi

Tue Dec 08 06:15 AM -- 06:30 AM (PST) @ Orals & Spotlights: Social/Privacy
in Orals & Spotlights Track 10: Social/Privacy »

We study the task of differentially private clustering. For several basic clustering problems, including Euclidean DensestBall, 1-Cluster, k-means, and k-median, we give efficient differentially private algorithms that achieve essentially the same approximation ratios as those that can be obtained by any non-private algorithm, while incurring only small additive errors. This improves upon existing efficient algorithms that only achieve some large constant approximation factors.

Our results also imply an improved algorithm for the Sample and Aggregate privacy framework. Furthermore, we show that one of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.

Author Information

Badih Ghazi (Google)
Ravi Kumar (Google)
Pasin Manurangsi (Google)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors