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

CREATORSumegha Garg, Songhua He, Periklis A. Papakonstantinou
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE163194
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.23104

Browse the full library · About the Tower of Babel