In this paper we present efficient pseudodeterministic algorithms for both the global minimum cut and minimum s-t cut problems. The running time of our algorithm for the global minimum cut problem is asymptotically better than the fastest sequential deterministic global minimum cut algorithm (Henzinger, Li, Rao, Wang; SODA 2024). Furthermore, we implement our algorithm in streaming, PRAM, and cut-query models, where no efficient deterministic global minimum cut algorithms are known.

Linear matroid intersection is an important problem in combinatorial optimization. Given two linear matroids over the same ground set, the linear matroid intersection problem asks you to find a common independent set of maximum size. The deep interest in linear matroid intersection is due to the fact that it generalises many classical problems in theoretical computer science, such as bipartite matching, edge disjoint spanning trees, rainbow spanning tree, and many more. We study this problem in the model of catalytic computation: space-bounded machines are granted access to \textit{catalytic space}, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation. Although linear matroid intersection has had a polynomial time algorithm for over 50 years, it remains an important open problem to show that linear matroid intersection belongs to any well studied subclass of $\mathsf{P}$. We address this problem for the class catalytic logspace ($\mathsf{CL}$) with a polynomial time bound ($\mathsf{CLP}$). Recently, Agarwala and Mertz (2025) showed that bipartite maximum matching can be computed in the class $\mathsf{CLP}\subseteq \mathsf{P}$. This was the first subclass of $\mathsf{P}$ shown to contain bipartite matching, and additionally the first problem outside $\mathsf{TC}^1$ shown to be contained in $\mathsf{CL}$. We significantly improve the result of Agarwala and Mertz by showing that linear matroid intersection can be computed in $\mathsf{CLP}$.

Matching is a central problem in theoretical computer science, with a large body of work spanning the last five decades. However, understanding matching in the time-space bounded setting remains a longstanding open question, even in the presence of additional resources such as randomness or non-determinism. In this work we study space-bounded machines with access to catalytic space, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation. Despite this heavy restriction, many recent works have shown the power of catalytic space, its utility in designing classical space-bounded algorithms, and surprising connections between catalytic computation and derandomization. Our main result is that bipartite maximum matching (MATCH) can be computed in catalytic logspace (CL) with a polynomial time bound (CLP). Moreover, we show that MATCH can be reduced to the lossy coding problem for NC circuits (LOSSY[NC]). This has consequences for matching, catalytic space, and derandomization:•Matching: this is the first well studied subclass of P which is known to contain MATCH, as well as the first algorithm simultaneously using sublinear free space and polynomial time with any additional resources. Thus, it gives a potential path to designing stronger space and time-space bounded algorithms.•Catalytic space: this is the first new problem shown to be in CL since the model was defined, and one which is extremely central and well-studied. Furthermore, it implies a strong barrier to showing CL lies anywhere in the NC hierarchy, and suggests to the contrary that CL is even more powerful than previously believed.•Derandomization: we give the first class C beyond Logspace for which we exhibit a natural problem in LOSSY[C] which is not known to be in C, as well as a full derandomization of the isolation lemma in CL in the context of MATCH. This also suggests a possible approach to derandomizing the famed RNC algorithm for MATCH.Our proof combines a number of strengthened ideas from isolation-based algorithms for matching alongside the compress-or-random framework in catalytic computation.