5 papers
An Efficient Private Algorithm for Community Detection
Vincent Cohen-Addad, Alessandro Epasto, Haim Kaplan +2
In this paper, we study the community detection problem in the stochastic block model (SBM) under privacy constraints. We introduce private and highly efficient algorithms for exac…
Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions
Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni +1
A soft-max function has two main efficiency measures: (1) approximation - which corresponds to how well it approximates the maximum function, (2) smoothness - which shows how sensi…
Differentially Private Clustering in Data Streams
Alessandro Epasto, Tamalika Mukherjee, Peilin Zhong
Clustering problems (such as -means and -median) are fundamental unsupervised machine learning primitives, and streaming clustering algorithms have been extensively studied i…
Scalable Private Partition Selection via Adaptive Weighting
Justin Y. Chen, Vincent Cohen-Addad, Alessandro Epasto +1
In the differentially private partition selection problem (a.k.a. private set union, private key discovery), users hold subsets of items from an unbounded universe. The goal is to…
Scalable contribution bounding to achieve privacy
Vincent Cohen-Addad, Alessandro Epasto, Jason Lee +1
In modern datasets, where single records can have multiple owners, enforcing user-level differential privacy requires capping each user's total contribution. This "contribution bou…