Weekly Bulletin

In this talk, we present an improved approximation algorithm for hierarchical correlation clustering. Given L layers of complete graphs on a common vertex set V, where each edge is labeled either + or -, the problem is to compute a clustering of V for each layer so that lower-layer clusterings refine upper-layer ones and the total weighted number of disagreements over all layers is minimized. Here, a + edge is counted as a disagreement if its endpoints are separated, and a - edge if its endpoints are placed in the same cluster. This problem is both a natural generalization of correlation clustering (the case L=1) and a formulation of the L1 ultrametric fitting problem arising in numerical taxonomy. Unlike the single-layer setting, for which substantial algorithmic progress has been made in recent years, the hierarchical case has seen little progress since the first constant-factor approximation algorithm of Cohen-Addad, Das, Kipouridis, Parotsidis, and Thorup. We give a new LP-rounding algorithm achieving an approximation ratio of 25.8, significantly improving the previous guarantee. Joint work with Mong-Jen Kao, Changyeol Lee, and Mu-Ting Lee (FOCS '25).

The definition of lattice polarized K3 surfaces has recently changed. I will attempt to explain the modified theory by Alexeev and Engel and its consequences with a particular focus on the intersection theory of Noether-Lefschetz cycles.