Lower Bounds for Non-adaptive Local Computation Algorithms

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.