We study streaming algorithms for the maximum directed cut problem. The edges of an n-vertex directed graph arrive one by one in an arbitrary order, and the goal is to estimate the value of the maximum directed cut using a single pass and small space. With O(n) space, a (1−ε)-approximation can be trivially obtained for any fixed ε > 0 using additive cut sparsifiers. The question that has attracted significant attention in the literature is the best approximation achievable by algorithms that use truly sublinear (i.e., n1−Ω(1)) space. A lower bound of Kapralov and Krachun (STOC’19) implies .5-approximation is the best one can hope for. The current best algorithm for general graphs obtains a .485-approximation due to the work of Saxena, Singer, Sudan, and Velusamy (FOCS’23). The same authors later obtained a (1/2−ε)-approximation, assuming that the graph is constant-degree (SODA’25). In this paper, we show that for any ε > 0, a (1/2−ε)-approximation of maximum dicut value can be obtained with n1−Ωε(1) space in *general graphs*. This shows that the lower bound of Kapralov and Krachun is generally tight, settling the approximation complexity of this fundamental problem. The key to our result is a careful analysis of how correlation propagates among high- and low-degree vertices, when simulating a suitable local algorithm.

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.

How many adjacency matrix queries (also known as pair queries) are required to estimate the size of a maximum matching in an n-vertex graph G ? We study this fundamental question in this paper.On the upper bound side, an algorithm of Bhattacharya, Kiss, and Saranurak [FOCS’23] gives an estimate that is within $\varepsilon n$ of the right bound with $n^{2-\Omega_{\varepsilon}(1)}$ queries, which is subquadratic in n (and thus sublinear in the matrix size) for any fixed $\varepsilon\gt0$. On the lower bound side, while there has been a lot of progress in the adjacency list model, no non-trivial lower bound has been established for algorithms with adjacency matrix query access. In particular, the only known lower bound is a folklore bound of $\Omega(n)$, leaving a huge gap.In this paper, we present the first superlinear in n lower bound for this problem. In fact, we close the gap mentioned above entirely by showing that the algorithm of [BKS’23] is optimal. Formally, we prove that for any fixed $\delta\gt0$, there is a fixed $\varepsilon\gt0$ such that an estimate that is within $\varepsilon n$ of the true bound requires $\Omega\left(n^{2-\delta}\right)$ adjacency matrix queries.Our lower bound also has strong implications for estimating the earth mover’s distance between distributions. For this problem, Beretta and Rubinstein [STOC’24] gave an $n^{2-\Omega_{\varepsilon}(1)}$ time algorithm that obtains an additive $\varepsilon$-approximation and works for any distance function. Whether this can be improved generally, or even for metric spaces, had remained open. Our lower bound rules out the possibility of any improvements over this bound, even under the strong assumption that the underlying distances are in a (1, 2)-metric.

We study the minimum spanning tree (MST) problem in the massively parallel computation (MPC) model. Our focus is particularly on the strictly sublinear regime of MPC where the space per machine is O (nδ ). Here n is the number of vertices and constant δ ∊ (0, 1) can be made arbitrarily small. The MST problem admits a simple and folklore O (log n )-round algorithm in the MPC model. When the weights can be arbitrary, this matches a conditional lower bound of Ω(log n ) which follows from a well-known 1vs2-Cycle conjecture. As such, much of the literature focuses on breaking the logarithmic barrier in more structured variants of the problem, such as when the vertices correspond to points in low- [2, STOC’14] or high-dimensional Euclidean spaces [28, SODA’24].

Maximum matching is one of the most fundamental combinatorial optimization problems with applications in various contexts such as balanced clustering, data mining, resource allocation, and online advertisement. In many of these applications, the input graph is massive. The sheer size of these inputs makes it impossible to store the whole graph in the memory of a single machine and process it there. Graph sparsification has been an extremely powerful tool to alleviate this problem. In this paper, we study a highly successful and versatile sparsifier for the matching problem: the *edge-degree constrained subgraph (EDCS)* introduced first by Bernstein & Stein 2015 The EDCS has a parameter $\beta \geq 2$ which controls the density of the sparsifier. It has been shown through various proofs in the literature that by picking a subgraph with $O(n\beta)$ edges, the EDCS includes a matching of size at least $2/3-O(1/\beta)$ times the maximum matching size. As such, by increasing $\beta$ the approximation ratio of EDCS gets closer and closer to $2/3$. In this paper, we propose a new approach for analyzing the approximation ratio of EDCS. Our analysis is *tight* for any value of $\beta$. Namely, we pinpoint the precise approximation ratio of EDCS for any sparsity parameter $\beta$. Our analysis reveals that one does not necessarily need to increase $\beta$ to improve approximation, as suggested by previous analysis. In particular, the best choice turns out to be $\beta = 6$, which achieves an approximation ratio of $.677$! This is arguably surprising as it is even better than $2/3 \sim .666$, the bound that was widely believed to be the limit for EDCS.

We study maximum matchings in fully dynamic graphs, which are graphs that undergo both edge insertions and deletions. Our focus is on algorithms that estimate the size of maximum matching after each update while spending a small time.

We study the robust communication complexity of maximum matching. Edges of an arbitrary $n$-vertex graph $G$ are randomly partitioned between Alice and Bob independently and uniformly. Alice has to send a single message to Bob such that Bob can find an (approximate) maximum matching of the whole graph $G$. We specifically study the best approximation ratio achievable via protocols where Alice communicates only $\widetilde{O}(n)$ bits to Bob. There has been a growing interest on the robust communication model due to its connections to the random-order streaming model. An algorithm of Assadi and Behnezhad [ICALP'21] implies a $(2/3+ε_0 \sim .667)$-approximation for a small constant $0 < ε_0 < 10^{-18}$, which remains the best-known approximation for general graphs. For bipartite graphs, Assadi and Behnezhad [Random'21] improved the approximation to .716 albeit with a computationally inefficient (i.e., exponential time) protocol. In this paper, we study a natural and efficient protocol implied by a random-order streaming algorithm of Bernstein [ICALP'20] which is based on edge-degree constrained subgraphs (EDCS) [Bernstein and Stein; ICALP'15]. The result of Bernstein immediately implies that this protocol achieves an (almost) $(2/3 \sim .666)$-approximation in the robust communication model. We present a new analysis, proving that it achieves a much better (almost) $(5/6 \sim .833)$-approximation. This significantly improves previous approximations both for general and bipartite graphs. We also prove that our analysis of Bernstein's protocol is tight.