32 citations · 50 across the 21 of their papers we have counts for
25 papers
Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds
Deeparnab Chakrabarty, Aditi Dudeja, David Saulpic
We study the round complexity of learning a hidden partition of an -element universe using PAIR queries: PAIR() tells us whether and belong to the sam…
Terminal Dimension Reduction for Time Series with Applications
Alexander Munteanu, Matteo Russo, David Saulpic +1
Terminal embeddings have emerged as a powerful tool for dimension reduction. Given a set of points , a terminal embedding is a mapping $f:\mathbb{R}^d\righta…
Near-Optimal Bounds for Parameterized Euclidean k-means
Vincent Cohen-Addad, Karthik C. S., David Saulpic +1
The -means problem is a classic objective for modeling clustering in a metric space. Given a set of points in a metric space, the goal is to find representative points so as…
Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
Vincent Cohen-Addad, Karthik C. S., David Saulpic +1
The -median and -means clustering objectives are classic objectives for modeling clustering in a metric space. Given a set of points in a metric space, the goal of the -me…
Improved Lower Bounds for Privacy under Continual Release
Bardiya Aryanfard, Monika Henzinger, David Saulpic +1
We study the problem of continually releasing statistics of an evolving dataset under differential privacy. In the event-level setting, we show the first polynomial lower bounds on…
Differentially Private Federated -Means Clustering with Server-Side Data
Jonathan Scott, Christoph H. Lampert, David Saulpic
Clustering is a cornerstone of data analysis that is particularly suited to identifying coherent subgroups or substructures in unlabeled data, as are generated continuously in larg…