We study non-adaptive Local Computation Algorithms (LCA). A reduction of Parnas and Ron (TCS’07) turns any distributed algorithm into a non-adaptive LCA. Plugging known distributed algorithms, this leads to non-adaptive LCAs for constant approximations of maximum matching (MM) and minimum vertex cover (MVC) with complexity $\Delta^{O(\log \Delta / \log \log \Delta)}$, where $\Delta$ is the maximum degree of the graph. Allowing adaptivity, this bound can be significantly improved to $\operatorname{poly}(\Delta)$, but is such a gap necessary or are there better non-adaptive LCAs? Adaptivity as a resource has been studied extensively across various areas. Beyond this, we further motivate the study of non-adaptive LCAs by showing that even a modest improvement over the Parnas-Ron bound for the MVC problem would have major implications in the Massively Parallel Computation (MPC) setting. In particular, it would lead to faster truly sublinear space MPC algorithms for approximate MM, a major open problem of the area. Our main result is a lower bound that rules out this avenue for progress. Specifically, we prove that $\Delta^{\Omega(\log \Delta / \log \log \Delta)}$ queries are needed for any non-adaptive LCA computing a constant approximation of MM or MVC. This is the first separation between non-adaptive and adaptive LCAs, and already matches (up to constants in the exponent) the algorithm obtained by the black-box reduction of Parnas and Ron. Our proof blends techniques from two separate lines of work: sublinear time lower bounds and distributed lower bounds. Particularly, we adopt techniques such as couplings over acyclic subgraphs from the recent sublinear time lower bounds of Behnezhad, Roghani, and Rubinstein (STOC’23, FOCS’23, STOC’24). We apply these techniques on a very different instance, particularly (a modified version of) the construction of Kuhn, Moscibroda and Wattenhoffer (JACM’16) from distributed computing. Our proof reveals that the (modified) KMW instance has the rather surprising property that any random walk of any length has a tiny chance $\left(\Delta^{-\Omega(\log \Delta / \log \log \Delta)}\right)$ of identifying a matching edge. In contrast, the work of KMW only proves that short walks (i.e., walks of depth $O(\log \Delta / \log \log \Delta)$) are not useful.

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 the fully dynamic maximum matching problem. In this problem, the goal is to efficiently maintain an approximate maximum matching of a graph that is subject to edge insertions and deletions. Our focus is particularly on algorithms that maintain the edges of a$(1-\varepsilon)$-approximate maximum matching for an arbitrarily small constant$\varepsilon > 0$. Until recently, the fastest known algorithm for this problem required$\Theta(n)$time per update where$n$is the number of vertices. This bound was slightly improved to$n/(\log^{\ast}n)^{\Omega(1)}$by Assadi, Behnezhad, Khanna, and Li [STOC'23] and very recently to$n/2_{-}^{\Omega(\sqrt{\log n})}$by Liu [FOCS'24]. Whether this can be improved to$n^{1-\Omega(1)}$remains a major open problem. In this paper, we introduce Ordered Ruzsa-Szemerédi (ORS) graphs (a generalization of Ruzsa-Szemerédi graphs) and show that the complexity of dynamic matching is closely tied to them. For$\delta > 0$, define ORS$(\delta n)$to be the maximum number of matchings$M_{1}, \ldots, 1M_{t}$, each of size$\delta n$, that one can pack in an n-vertex graph such that each matching$M_{i}$is an induced matching in subgraph$M_{1}\cup\ldots\cup M_{i}$. We show that there is a randomized algorithm that maintains a$(1-\varepsilon)$-approximate maximum matching of a fully dynamic graph in amortized update-time. While the value of$\text{ORS}(\Theta(n))$remains unknown and is only upper bounded by$n^{1-o(1)}$, the densest construction known from more than two decades ago only achieves$ORS (\Theta(n))\geq n^{1/\Theta(\log\log n)}=n^{o(1)}$[Fischer et al. STOC'02]. If this is close to the right bound, then our algorithm achieves an update-time of$\sqrt{n^{1+O(\varepsilon)}}^{-}$, resolving the aforementioned longstanding open problem in dynamic algorithms in a strong sense.