Pith. sign in

REVIEW 2 minor 4 references

Query Lower Bounds for Correlation Clustering under Memory Constraints

T0 review · 0 major / 2 minor · reviewed 2026-06-30 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Approximating correlation clustering cost within additive εn² requires Ω(n/ε²) adjacency-matrix queries.

desk verdict This paper starts the memory-query tradeoff study for correlation clustering with a tight Omega(n/eps^2) adjacency-query lower bound for additive approximation and a superlinear lower bound under memory limits in the random model. read the letter →

arxiv 2605.23104 v2 pith:N23BN6JK submitted 2026-05-21 cs.CC

Sumegha Garg , Songhua He , Periklis A. Papakonstantinou This is my paper · ORCID
classification cs.CC
keywords correlationclusteringquerylowerboundsmemoryconstraintsrandommodeladjacencymatrixqueriesapproximationalgorithmsgraphpartitioning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Correlation clustering requires partitioning vertices to minimize the total disagreements between edges and non-edges. The paper shows that any algorithm outputting a partition with cost within additive εn² of the optimum must make Ω(n/ε²) queries to the adjacency matrix. When the algorithm is also memory-constrained, even the easier task of approximating the optimal cost value (without outputting the partition) requires asymptotically more than n/ε² queries in the random query model. The work also establishes the first lower bound in the general graph query model that permits adjacency-matrix, neighbor, and degree queries.

What carries the argument

Lower bounds on the number of adjacency-matrix queries needed in the random query model with memory limits to approximate the minimum disagreement cost of a vertex partition.

What would settle it

An algorithm that approximates the optimal clustering cost using o(n/ε²) adjacency-matrix queries while using limited memory in the random query model would falsify the lower bound.

Watch

Extended reading notes

Core claim

To output a partition whose cost approximates the optimum up to an additive error of εn², any algorithm requires Ω(n/ε²) adjacency-matrix queries. Under memory constraints, even approximating the optimal clustering cost requires ≫ n/ε² queries in the random query model. A first lower bound holds in the general graph query model allowing adjacency-matrix, neighbor, and degree queries.

Load-bearing premise

Algorithms are restricted to the random query model or general graph query model, and approximation error is measured additively relative to n².

Editorial extensions

If this is right

  • Any algorithm producing an approximate partition must use at least Ω(n/ε²) adjacency-matrix queries.
  • Memory limits raise the query requirement for even cost estimation above the memory-unconstrained case.
  • The general graph query model also requires a superlinear number of queries for correlation clustering.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Similar memory-query tradeoffs are likely to appear in other graph partitioning tasks such as community detection.
  • New algorithm designs that explicitly manage memory while sampling queries may be needed to approach the lower bounds.
  • The gap between the random-query and general-graph-model bounds points to room for tighter characterizations of allowed query types.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The paper initiates the study of memory-query tradeoffs for graph problems, focusing on correlation clustering. It proves a tight Ω(n/ε²) lower bound on adjacency-matrix queries to output a partition approximating the optimal cost to additive εn² error. It further shows that, under memory constraints, approximating the optimal clustering cost alone requires ≫ n/ε² queries in the random query model, and establishes the first query lower bound in the general graph model (allowing adjacency-matrix, neighbor, and degree queries). The latter two bounds are stated to not yet be tight.

Significance. If the proofs hold, the results are significant for establishing fundamental query lower bounds in correlation clustering and for opening the area of memory-query tradeoffs on graph problems. The tight Ω(n/ε²) bound (with an implied matching upper bound) and the first general-graph-model result are notable contributions; the memory-constrained super-linear bound, while not tight, highlights a concrete separation.

minor comments (2)
  1. [Abstract] The abstract and introduction should explicitly state or cite the matching O(n/ε²) upper bound that makes the first lower bound tight, including the model in which the upper bound holds.
  2. Clarify the precise memory constraint (e.g., o(n) bits or o(n log n) bits) used for the ≫ n/ε² claim in the random-query model, and whether it applies to the algorithm's internal state or only to the query access pattern.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work, the recognition of its significance in establishing query lower bounds for correlation clustering, and the recommendation for minor revision. No specific major comments were listed in the report, so we have no individual points requiring detailed rebuttal at this time. We will incorporate any minor editorial suggestions during the revision process.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity

full rationale

The paper derives query lower bounds for correlation clustering via standard information-theoretic and reduction arguments in the random-query and general graph query models. These techniques are external to the target result, draw on established query-complexity frameworks, and contain no self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations that reduce the claimed bounds to the paper's own inputs by construction. The derivation remains self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

No free parameters or new entities introduced; the work relies on standard query complexity assumptions and techniques.

assumptions (1)
  • domain assumption Definitions of the random query model and general graph model for querying graphs
    The lower bounds are proven in these standard models.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Query Lower Bounds for Correlation Clustering under Memory Constraints." pith.science (2026). https://pith.science/paper/N23BN6JK

@misc{pith2026260523104,
  author       = {Pith},
  title        = {Pith review of: Query Lower Bounds for Correlation Clustering under Memory Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/N23BN6JK}},
  note         = {Machine review of arXiv:2605.23104}
}
abstract

This 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 $\Omega(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.

Figures

Figures reproduced from arXiv: 2605.23104 by the authors.

Figure 1
Figure 1. Structure of distributions used in the lower bound proof [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. To obtain (G′ , C ′ ) from (G, C), v and w exchange their clusters, and swap their edges connected to the two clusters Cα and Cβ. The induced bipartite subgraph G′ [C ′ α, C′ β ] remains a regular bipartite graph. To show that |Sσ,u,v| is at most O(1/k) of |S′ σ,u,v|, we will construct a relation between Sσ,u,v and S ′ σ,u,v such that (i) each element in Sσ,u,v relates to at least Ω(n) elements in S ′ σ,u,v; (ii) ea… view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

  1. [1]

    Streaming algorithms and lower bounds forestimatingcorrelationclusteringcost

    3 [ASW23] Sepehr Assadi, Vihan Shah, and Chen Wang. Streaming algorithms and lower bounds forestimatingcorrelationclusteringcost. InAliceOh, TristanNaumann, AmirGlober- son, Kate Saenko, Moritz Hardt, and Sergey Levine, editors,Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Pro- cessing Systems 2023, NeurIPS ...

    work page 2023

  2. [2]

    Approximating max- imum matching requires almost quadratic time

    2, 4 [BRR24] Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Approximating max- imum matching requires almost quadratic time. InProceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 444–454, 2024. 30 [CALLN23] Vincent Cohen-Addad, Euiwoong Lee, Shi Li, and Alantha Newman. Handling corre- latedroundingerrorviaprecluste...

    work page 2024

  3. [3]

    A(3 +ε)- approximatecorrelationclusteringalgorithmindynamicstreams

    2 [CKL+24] Mélanie Cambus, Fabian Kuhn, Etna Lindy, Shreyas Pai, and Jara Uitto. A(3 +ε)- approximatecorrelationclusteringalgorithmindynamicstreams. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2861–

    work page 2024

  4. [4]

    2 [CMSY15] Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev

    SIAM, 2024. 2 [CMSY15] Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. Nearoptimallproundingalgorithmforcorrelationclusteringoncompleteandcomplete k-partite graphs. InProceedings of the 47th annual ACM Symposium on Theory of Computing (STOC), pages 219–228, 2015. 2 [Din24] Itai Dinur. Time-space lower bounds for bounded-err...

    work page 2024

Pith tools

Reviewed June 30, 2026 · model on record in the stance chip above.