{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreibu45kt4e77astdw4edma5n5yqlu5yy4i6rnwufdbozbu4sazwizi",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mfbblv7acum2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.17488v1",
  "publishedAt": "2026-02-20T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Badih Ghazi",
    "Cristóbal Guzmán",
    "Pritish Kamath",
    "Alexander Knop",
    "Ravi Kumar",
    "Pasin Manurangsi"
  ],
  "textContent": "**Authors:** Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi\n\nWe 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"
}