Query Lower Bounds for Correlation Clustering under Memory Constraints
Sumegha Garg, Songhua He, Periklis A. Papakonstantinou · 2026
Read Query Lower Bounds for Correlation Clustering under Memory Constraints by Sumegha Garg, Songhua He, Periklis A. Papakonstantinou (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-23104.txt.
Introduction
Garg, He, and Papakonstantinou open memory-query trade-offs for correlation clustering. That task partitions to minimize disagreements: non-edges inside clusters, edges across. Their first result is a tight bound: to output a partition near optimal cost, any algorithm needs order n over epsilon squared queries. Under memory limits, even approximating optimal cost alone needs far more queries under random queries. They also prove the first general lower bound, allowing matrix, neighbor, and degree queries, though two bounds are not yet tight.
Catalog record
| CREATOR | Sumegha Garg, Songhua He, Periklis A. Papakonstantinou |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 163194 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.23104