Shreyas Pai

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time

We study the dynamic correlation clustering problem with *adaptive* edge label flips. In correlation clustering, we are given a $n$-vertex complete graph whose edges are labeled either $(+)$ or $(-)$, and the goal is to minimize the total number of $(+)$ edges between clusters and the number of $(-)…