The study of space-bounded computation is a central theme in complexity theory, with a long line of work investigating the power and limitations of logarithmic-space algorithms. A recent direction in this area focuses on models that augment classical space bounds with auxiliary resources, such as catalytic space, where a large workspace is available but must be returned to its initial state at the end of the computation. This model, introduced by Buhrman, Cleve, Koucký, Loff, and Speelman [STOC 2014], has led to surprising algorithmic developments and a refined understanding of the role of reversibility and space reuse in computation. One of the striking algorithmic results in this area is that bipartite maximum matching can be computed in catalytic logspace (CL) [Aggarwala and Mertz, FOCS 25].
We show that the size of a maximum matching in general graphs can be determined in CL. Our algorithm is based on a linear-algebraic algorithm for maximum matching by Geelen [2000]. We then show that this algorithm, along with some new ideas, can be used to find (in CL) a maximum matching in general graphs."This is joint work with Samir Datta, Srijan Chakraborty, Aryan Kusre and Partha Mukhopadhyay."
Bio: Amit Sinhababu is an assistant professor in Chennai Mathematical Institute. He did PhD from IIT Kanpur under the supervision of Nitin Saxena and was a postdoctoral fellow at University of Aalen and Ulm mentored by Thomas Thierauf. Amit's research interests are broadly in algebraic techniques in complexity theory and algorithms.
