8 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…
Faster and Simpler Greedy Algorithm for -Median and -Means
Max Dupré la Tour, David Saulpic
Clustering problems such as -means and -median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects. In…
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…