2026-07-20T14:23:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25972 2026-06-23T13:06:47Z ddc:004 open_access

Computational Hardness of Private Coreset Ghazi, Badih Guzmán, Cristóbal Kamath, Pritish Knop, Alexander Kumar, Ravi Manurangsi, Pasin Differentially Private Clustering Coreset Cryptographic Hardness 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 ± α) 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 𝓁_∞-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 α = Θ(1/d²), where d is the dimension. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Badih Ghazi and Cristóbal Guzmán and Pritish Kamath and Alexander Knop and Ravi Kumar and Pasin Manurangsi 2026 Is Part Of LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FORC.2026.1 urn:nbn:de:0030-drops-259725 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.1 eng https://creativecommons.org/licenses/by/4.0/legalcode