{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreifkrdhg6xrfrbevung57umwlfzzr7sl3246g6sow524pjqxhr5f2u",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mmnyqivg4qi2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.23104v1",
  "publishedAt": "2026-05-25T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Sumegha Garg",
    "Songhua He",
    "Periklis A. Papakonstantinou"
  ],
  "textContent": "**Authors:** Sumegha Garg, Songhua He, Periklis A. Papakonstantinou\n\nThis work initiates the study of memory-query tradeoffs for graph problems, with a focus on correlation clustering. Correlation clustering asks for a partition of the vertices that minimizes disagreements: non-edges inside clusters plus edges across clusters. Our first result is a tight query lower bound: to output a partition whose cost approximates the optimum up to an additive error of $\\varepsilon n^2$, any algorithm requires $Ω(n/\\varepsilon^2)$ adjacency-matrix queries. Under memory constraints, we show that even for the seemingly easier task of approximating the optimal clustering cost (without producing a partition), any algorithm in the random query model must make $\\gg n/\\varepsilon^2$ adjacency-matrix queries. Finally, we prove the first general graph model query lower bound for correlation clustering, where algorithms are allowed adjacency-matrix, neighbor, and degree queries. The latter two bounds are not yet tight, leaving room for sharper results.",
  "title": "Query Lower Bounds for Correlation Clustering under Memory Constraints"
}