109 citations · 266 across the 23 of their papers we have counts for
24 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…
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…
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…
Perturb-and-Project: Differentially Private Similarities and Marginals
Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto +2
We revisit the input perturbations framework for differential privacy where noise is added to the input and the result is then projected back to the space of adm…
A Scalable Algorithm for Individually Fair K-means Clustering
MohammadHossein Bateni, Vincent Cohen-Addad, Alessandro Epasto +1
We present a scalable algorithm for the individually fair (, )-clustering problem introduced by Jung et al. and Mahabadi et al. Given points in a metric space, let $δ…
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…
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees
Jacob Imola, Alessandro Epasto, Mohammad Mahdian +2
Hierarchical Clustering is a popular unsupervised machine learning method with decades of history and numerous applications. We initiate the study of differentially private approxi…
Differentially Private Continual Releases of Streaming Frequency Moment Estimations
Alessandro Epasto, Jieming Mao, Andres Munoz Medina +3
The streaming model of computation is a popular approach for working with large-scale data. In this setting, there is a stream of items and the goal is to compute the desired quant…
Private estimation algorithms for stochastic block models and mixture models
Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi +4
We introduce general tools for designing efficient private estimation algorithms, in the high-dimensional settings, whose statistical guarantees almost match those of the best know…
Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank
Alessandro Epasto, Vahab Mirrokni, Bryan Perozzi +2
Personalized PageRank (PPR) is a fundamental tool in unsupervised learning of graph representations such as node ranking, labeling, and graph embedding. However, while data privacy…
Smooth Anonymity for Sparse Graphs
Alessandro Epasto, Hossein Esfandiari, Vahab Mirrokni +1
When working with user data providing well-defined privacy guarantees is paramount. In this work, we aim to manipulate and share an entire sparse dataset with a third party private…
Scalable Differentially Private Clustering via Hierarchically Separated Trees
Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi +5
We study the private -median and -means clustering problem in dimensional Euclidean space. By leveraging tree embeddings, we give an efficient and easy to implement algor…
Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches
Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni +1
Streaming computation plays an important role in large-scale data analysis. The sliding window model is a model of streaming computation which also captures the recency of the data…
Massively Parallel and Dynamic Algorithms for Minimum Size Clustering
Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni +1
In this paper, we study the -gather problem, a natural formulation of minimum-size clustering in metric spaces. The goal of -gather is to partition points into clusters s…
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…
Fair Hierarchical Clustering
Sara Ahmadian, Alessandro Epasto, Marina Knittel +6
As machine learning has become more prevalent, researchers have begun to recognize the necessity of ensuring machine learning systems are fair. Recently, there has been an interest…
Sliding Window Algorithms for k-Clustering Problems
Michele Borassi, Alessandro Epasto, Silvio Lattanzi +2
The sliding window model of computation captures scenarios in which data is arriving continuously, but only the latest elements should be used for analysis. The goal is to desi…
Fair Correlation Clustering
Sara Ahmadian, Alessandro Epasto, Ravi Kumar +1
In this paper, we study correlation clustering under fairness constraints. Fair variants of -median and -center clustering have been studied recently, and approximation algor…
Fair Correlation Clustering
Saba Ahmadi, Sainyam Galhotra, Barna Saha +1
In this paper we study the problem of correlation clustering under fairness constraints. In the classic correlation clustering problem, we are given a complete graph where each edg…
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto +4
Hierarchical Clustering is an unsupervised data analysis method which has been widely used for decades. Despite its popularity, it had an underdeveloped analytical foundation and t…
Clustering without Over-Representation
Sara Ahmadian, Alessandro Epasto, Ravi Kumar +1
In this paper we consider clustering problems in which each point is endowed with a color. The goal is to cluster the points to minimize the classical clustering cost but with the…
Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contexts
Alessandro Epasto, Bryan Perozzi
Recent interest in graph embedding methods has focused on learning a single representation for each node in the graph. But can nodes really be best described by a single vector rep…
Submodular Optimization over Sliding Windows
Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii +1
Maximizing submodular functions under cardinality constraints lies at the core of numerous data mining and machine learning applications, including data diversification, data summa…
TRIÈST: Counting Local and Global Triangles in Fully-dynamic Streams with Fixed Memory Size
Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato +1
We present TRIÈST, a suite of one-pass streaming algorithms to compute unbiased, low-variance, high-quality approximations of the global and local (i.e., incident to each vertex) n…