We design replicable algorithms in the context of statistical clustering under the recently
introduced notion of replicability from Impagliazzo et al.[2022]. According to this definition, a …

We design a new algorithm for the Euclidean k-means problem that operates in the local
model of differential privacy. Unlike in the non-private literature, differentially private …

In this work, we study high-dimensional mean estimation under user-level differential
privacy, and design an $(\varepsilon,\delta) $-differentially private mechanism using as few …

We provide an approximation algorithm for k-means clustering in the\emph {one-
round}(aka\emph {non-interactive}) local model of differential privacy (DP). Our algorithm …

Generating differentially private (DP) synthetic data that closely resembles the original
private data is a scalable way to mitigate privacy concerns in the current data-driven world …

In many applications, multiple parties have private data regarding the same set of users but
on disjoint sets of attributes, and a server wants to leverage the data to train a model. To …

Abstract Finding min $ s $-$ t $ cuts in graphs is a basic algorithmic tool, with applications in
image segmentation, community detection, reinforcement learning, and data clustering. In …

Clustering is a fundamental problem in data analysis. In differentially private clustering, the
goal is to identify k cluster centers without disclosing information on individual data points …

We study the differentially private (DP) $ k $-means and $ k $-median clustering problems of
$ n $ points in $ d $-dimensional Euclidean space in the massively parallel computation …

Given a set of $ n $ points in $\mathbb {R}^ d $, the goal of Euclidean $(k,\ell) $-clustering is
to find $ k $ centers that minimize the sum of the $\ell $-th powers of the Euclidean distance …