3 papers
cs.DS2026
Approximation Preserving Coresets
Milind Prabhu, Chris Schwiegelshohn, Sudarshan Shyam
Clustering in a big data setting is an intensively studied problem, with coresets emerging as one of the important paradigms in this line of work. Given a cost function $\text{cost…
cs.DS2025
Simple and Optimal Sublinear Algorithms for Mean Estimation
Beatrice Bertolotti, Matteo Russo, Chris Schwiegelshohn +1
We study the sublinear multivariate mean estimation problem in -dimensional Euclidean space. Specifically, we aim to find the mean of a ground point set , which minimize…
cs.CR2025
Distributed Differentially Private Data Analytics via Secure Sketching
Jakob Burkhardt, Hannah Keller, Claudio Orlandi +1
We introduce the linear-transformation model, a distributed model of differentially private data analysis. Clients have access to a trusted platform capable of applying a public ma…