A&C Seminar - Theory and applications of complete Min-CSPs: A case study in Correlation Clustering

Abstract: We will discuss recent algorithmic results on fundamental problems in data science and clustering, including Correlation Clustering, Low-Rank Approximation, and Metric Distance Violation. A unifying theme will be their connections to Minimum Constraint Satisfaction Problems (CSPs) in complete instances. Starting from the rich theory of dense Max CSPs with several algorithmic tools (e.g., convex hierarchy, random sampling, regularity lemma), we show how this theory can be augmented to handle minimization objectives in applied domains. These efforts also inspired a systematic study on Min-CSPs in complete instances.

As a technical example, we will highlight our results for Correlation Clustering, one of the most well-studied graph clustering problems. Bypassing the previous barrier of a 2-approximation based on the standard LP, we obtain a 1.44-approximation, first using a Sherali-Adams hierarchy, later also matched by a random sampling technique.