Establishes Ω(n/ε²) query lower bounds for approximating correlation clustering cost and partitions under memory constraints in adjacency-matrix and general graph models.
Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions , booktitle =
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
years
2026 2verdicts
UNVERDICTED 2representative citing papers
LAPRAS uses predictions to answer likely queries with the offline Matrix Mechanism and paces residual budget for unpredicted queries via unbiased stopping-time estimation from the first few unexpected arrivals, achieving near-offline utility when overlap is high.
citing papers explorer
-
Query Lower Bounds for Correlation Clustering under Memory Constraints
Establishes Ω(n/ε²) query lower bounds for approximating correlation clustering cost and partitions under memory constraints in adjacency-matrix and general graph models.
-
LAPRAS : Learning-Augmented PRivate Answering for linear query Streams
LAPRAS uses predictions to answer likely queries with the offline Matrix Mechanism and paces residual budget for unpredicted queries via unbiased stopping-time estimation from the first few unexpected arrivals, achieving near-offline utility when overlap is high.