Sublinear algorithms for correlation clustering

Given a graph with positive and negative edge labels, the correlation clustering problem aims to cluster the vertices so as to minimize the total number of between-cluster positive and within-cluster negative edges. I will present a recent result that computes a 3+eps approximation in O(Delta/eps) LCA probes where Delta is the maximum degree, O(log 1/eps) MPC rounds, and O(1/eps) expected update time in the fully dynamic setting under oblivious adversary.
It might be of independent interest that one of the technical results recovers the guarantee obtained by the seminal work of Yoshida, Yamamoto, and Ito [STOC 2009] for computing the maximal independent set in the LCA model. A large part of my talk will focus on analyzing that technical result.
Based on joint work with Mina Dalirrooyfard and Konstantin Makarychev.