Computational Hardness of Private Coreset
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918345788358656 |
|---|---|
| author | Ghazi, Badih Guzmán, Cristóbal Kamath, Pritish Knop, Alexander Kumar, Ravi Manurangsi, Pasin |
| author_facet | Ghazi, Badih Guzmán, Cristóbal Kamath, Pritish Knop, Alexander Kumar, Ravi Manurangsi, Pasin |
| contents | We study the problem of differentially private (DP) computation of coreset for the $k$-means objective. For a given input set of points, a coreset is another set of points such that the $k$-means objective for any candidate solution is preserved up to a multiplicative $(1 \pm α)$ factor (and some additive factor).
We prove the first computational lower bounds for this problem. Specifically, assuming the existence of one-way functions, we show that no polynomial-time $(ε, 1/n^{ω(1)})$-DP algorithm can compute a coreset for $k$-means in the $\ell_\infty$-metric for some constant $α> 0$ (and some constant additive factor), even for $k=3$. For $k$-means in the Euclidean metric, we show a similar result but only for $α= Θ\left(1/d^2\right)$, where $d$ is the dimension. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_17488 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Computational Hardness of Private Coreset Ghazi, Badih Guzmán, Cristóbal Kamath, Pritish Knop, Alexander Kumar, Ravi Manurangsi, Pasin Computational Geometry Cryptography and Security Data Structures and Algorithms We study the problem of differentially private (DP) computation of coreset for the $k$-means objective. For a given input set of points, a coreset is another set of points such that the $k$-means objective for any candidate solution is preserved up to a multiplicative $(1 \pm α)$ factor (and some additive factor). We prove the first computational lower bounds for this problem. Specifically, assuming the existence of one-way functions, we show that no polynomial-time $(ε, 1/n^{ω(1)})$-DP algorithm can compute a coreset for $k$-means in the $\ell_\infty$-metric for some constant $α> 0$ (and some constant additive factor), even for $k=3$. For $k$-means in the Euclidean metric, we show a similar result but only for $α= Θ\left(1/d^2\right)$, where $d$ is the dimension. |
| title | Computational Hardness of Private Coreset |
| topic | Computational Geometry Cryptography and Security Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.17488 |