We study the parallel complexity of finding a basis of a graphic matroid under independence-oracle access. Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988) initiated the study of this problem and established two algorithms for finding a spanning forest: one running in O(log m) rounds with m^{Θ(log m)} queries, and another, for any d ∈ ℤ^+, running in O(m^{2/d}) rounds with Θ(m^d) queries. A key open question they posed was whether one could simultaneously achieve polylogarithmic rounds and polynomially many queries. We give a deterministic algorithm that uses O(log m) adaptive rounds and poly(m) non-adaptive queries per round to return a spanning forest on m edges, and complement this result with a matching Ω(log m) lower bound for any (even randomized) algorithm with poly(m) queries per round. Thus, the adaptive round complexity for graphic matroids is characterized exactly, settling this long-standing problem. Beyond graphs, we show that our framework also yields an O(log m)-round, poly(m)-query algorithm for any binary matroid satisfying a smooth circuit counting property, implying, among others, an optimal O(log m)-round parallel algorithms for finding bases of cographic matroids. Finally, we conjecture a natural strengthening of known circuit-counting bounds for the much broader class of regular matroids and even an extension to so-called max-flow min-cut matroids; assuming it, our algorithm achieves the same O(log m) rounds and poly(m) queries for all such matroids - which includes graphic and cographic matroids as special cases.

In the fully dynamic maximal matching problem, the goal is to maintain a maximal matching in a graph undergoing an online sequence of edge insertions and deletions, while minimizing the update time. The problem has been studied extensively in the oblivious-adversary setting, where randomized algorithms with polylogarithmic worst-case and constant amortized update time have been known for some time. A major challenge in this area has been designing an algorithm with non-trivial update time against an adaptive adversary, who may explicitly tailor the update sequence to the algorithm’s choices. In a recent breakthrough, Bernstein, Bhattacharya, Kiss, and Saranurak (STOC 2025; hereafter, BBKS25) obtained the first algorithms with sublinear in n update time for this setting: namely, a randomized algorithm with Õ(n3/4) amortized update time, and a deterministic algorithm with Õ(n8/9) amortized update time. Our main result is a deterministic algorithm for fully dynamic maximal matching with amortized update time n1/2+o(1).

A fundamental question in parallel computation, posed by Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988), asks: given only independence-oracle access to a matroid on n elements, how many adaptive rounds are required to find a basis using only polynomially many queries? This question generalizes, among others, the complexity of finding bases of linear spaces, partition matroids, and spanning forests in graphs. In their work, they established an upper bound of $O(\sqrt{n})$ rounds and a lower bound of $\widetilde{\Omega}\left(n^{1 / 3}\right)$ rounds for this problem, and these bounds have remained unimproved since then. In this work, we make the first progress in narrowing this gap by designing a parallel algorithm that finds a basis of an arbitrary matroid in $\tilde{O}\left(n^{7 / 15}\right)$ rounds (using polynomially many independence queries per round) with high probability, surpassing the long-standing $O(\sqrt{n})$ barrier. Our approach introduces a novel matroid decomposition technique and other structural insights that not only yield this general result but also lead to a much improved new algorithm for the class of partition matroids (which underlies the $\widetilde{\Omega}\left(n^{1 / 3}\right)$ lower bound of Karp, Upfal, and Wigderson). Specifically, we develop an $\tilde{O}\left(n^{1 / 3}\right)$-round algorithm, thereby settling the round complexity of finding a basis in partition matroids. As a further application, we also improve the parallel complexity of the classic matroid intersection problem. By plugging our basis-finding algorithm into a known algorithmic framework for matroid intersection, we obtain an $\tilde{O}\left(n^{37 / 45}\right)$ round algorithm for matroid intersection, improving upon the prior $O\left(n^{5 / 6}\right)$ bound. Collectively, these results represent the first progress on the parallel complexity of finding matroid bases in 40 years, and we believe that techniques developed here may prove useful for other problems on matroids.