We study the classic correlation clustering problem. Given $n$ objects and a complete labeling of the object-pairs as either “similar” or “dissimilar”, the goal is to partition the objects into arbitrarily many clusters while minimizing disagreements with the labels. A classic Pivot algorithm for this problem, due to [Ailon et al STOC'05], obtains a 3-approximation for this problem. Over the years, this algorithm has been successfully implemented in various settings. The downside of the Pivot algorithm is that the approximation analysis of 3 is tight for it. While better approximations have been achieved in some settings, these algorithms are often hard to implement in various settings. For example, [Behnezhad et al FOCS19] showed that the output of Pivot can be maintained in polylog time per update in a dynamic setting, a bound that was improved to constant by [Dalirrooyfard et al ICML'24]. But obtaining a better approximation remains open. In this paper, we present Modified Pivot, an algorithm that locally improves the output of Pivot. Our Modified Pivot algorithm can be implemented just as efficiently as Pivot in various settings. Our experiments show that the output of Modified Pivot on average makes less than 77\% of the mistakes made by Pivot. More surprisingly, we prove theoretically that Modified Pivot has approximation ratio $3-\epsilon_0$ for some absolute constant $\epsilon_0 > 0$. This, e.g., leads to a better than 3 approximation in the dynamic setting in polylog time, improving the 3-approximation obtained by [Behnezhad et al FOCS'19] and [Dalirrooyfard et al ICML'24].

We study correlation clustering in the streaming setting. This problem has been studied extensively and numerous algorithms have been developed, most requiring multiple passes over the stream. For the important case of single-pass algorithms, recent work of Assadi and Wang [8] obtains a c-approximation using Õ(n) space where c > 105 is a constant and n is the number of vertices to be clustered. We present a single-pass algorithm that obtains a 5-approximation using O(n) space. The algorithm itself is extremely simple and has implications beyond the streaming setting (such as for dynamic and local computation algorithms). The approximation analysis, on the other hand, is delicate and in fact tight.

We study parallel algorithms for correlation clustering. Each pair among n objects is labeled as either “similar” or “dissimilar”. The goal is to partition the objects into arbitrarily many clusters while minimizing the number of disagreements with the labels.Our main result is an algorithm that for any $\varepsilon>0$ obtains a (3 + $\varepsilon$)-approximation in $O(1/\varepsilon$) rounds (of models such as massively parallel computation, local, and semi-streaming). This is a culminating point for the rich literature on parallel correlation clustering. On the one hand, the approximation (almost) matches a natural barrier of 3 for combinatorial algorithms. On the other hand, the algorithm’s round-complexity is essentially constant.To achieve this result, we introduce a simple $O(1/\varepsilon$)-round parallel algorithm. Our main result is to provide an analysis of this algorithm, showing that it achieves a (3 + $\varepsilon$)-approximation. Our analysis draws on new connections to sublinear-time algorithms. Specifically, it builds on the work of Yoshida, Yamamoto, and Ito [1] on bounding the “query complexity” of greedy maximal independent set. To our knowledge, this is the first application of this method in analyzing the approximation ratio of any algorithm.Full version. Due to the page limit, this version of the paper does not include all the proofs. The full version of the paper is available at [2].

We give a randomness-efficient Massively Parallel Computation (MPC) algorithm for deciding whether an undirected graph is connected. For Connectivity on n-vertex, m-edge graphs whose components have diameter at most D = 2o(log n/ log log n), our algorithm runs in R = O(log D + log logm/n,.n) rounds and uses a total of (log n)O(R) random bits, O(m) machines, and n1-Ω(1) space per machine with good probability.1 With good probability means with probability at least 1 - 1/poly ((m log n)/n), which is the same as in Liu, Tarjan, and Zhong (SPAA '20). Our algorithm achieves a super-polynomial saving in randomness complexity as compared to the breakthrough algorithm of Andoni et al. (FOCS '18) and the subsequent improvement by Behnezhad et al. (FOCS '19). Our algorithm has the same round complexity as that of Behnezhad et al., but uses more total space.

The randomized query complexity 𝖱(f) of a boolean function f: {0,1}ⁿ → {0,1} is famously characterized (via Yao’s minimax) by the least number of queries needed to distinguish a distribution 𝒟₀ over 0-inputs from a distribution 𝒟₁ over 1-inputs, maximized over all pairs (𝒟₀,𝒟₁). We ask: Does this task become easier if we allow query access to infinitely many samples from either 𝒟₀ or 𝒟₁? We show the answer is no: There exists a hard pair (𝒟₀,𝒟₁) such that distinguishing 𝒟₀^∞ from 𝒟₁^∞ requires Θ(𝖱(f)) many queries. As an application, we show that for any composed function f∘g we have 𝖱(f∘g) ≥ Ω(fbs(f)𝖱(g)) where fbs denotes fractional block sensitivity.

We consider unconditional lower bounds in the Adaptive Massively Parallel Computation (AMPC) model introduced by Behnezhad et al. (SPAA 19), which is an adaptive variant of the Massively Parallel Computation (MPC) model. Our first contribution is an optimal lower bound on the round complexity of distinguishing whether an input graph is a cycle of length n or two cycles of length n/2. This problem, 1v2-CIRCLE, has emerged as a central problem in the study of modern massively parallel computation. We prove that any AMPC algorithm for the 1v2-CIRCLE problem with I/O capacity O(nε) per machine requires Ω(1/ε) rounds, matching the upper bound of Behnezhad et al.

Phylogenetic tree reconciliation is an important technique for reconstructing the evolutionary histories of species and genes and other dependent entities. Reconciliation is typically performed in a maximum parsimony framework and the number of optimal reconciliations can grow exponentially with the size of the trees, making it difficult to understand the solution space. This paper demonstrates how a small number of reconciliations can be found that collectively contain the most highly supported events in the solution space. While we show that the formal problem is NP-complete, we give a approximation algorithm, experimental results that indicate its effectiveness, and the new DTL-RnB software tool that uses our algorithms to summarize the space of optimal reconciliations (www.cs.hmc.edu/dtlrnb).

BACKGROUND: Maximum parsimony phylogenetic tree reconciliation is an important technique for reconstructing the evolutionary histories of hosts and parasites, genes and species, and other interdependent pairs. Since the problem of finding temporally feasible maximum parsimony reconciliations is NP-complete, current methods use either exact algorithms with exponential worst-case running time or heuristics that do not guarantee optimal solutions. RESULTS: We offer an efficient new approach that begins with a potentially infeasible maximum parsimony reconciliation and iteratively "repairs" it until it becomes temporally feasible. CONCLUSIONS: In a non-trivial number of cases, this approach finds solutions that are better than those found by the widely-used Jane heuristic.