Programming news · September 2025
A classic matroid problem is shown to fit in catalytic logspace
Aryan Agarwala, Yaroslav Alekseev and Antoine Vinciguerra show that linear matroid intersection belongs to catalytic logspace with polynomial time, a model in which an algorithm borrows a large pre-filled memory tape but must restore it bit-for-bit when it finishes.
Linear matroid intersection generalises bipartite matching and spanning-tree problems, and although polynomial-time algorithms have existed for over fifty years, pinning it to a tight, well-studied subclass had remained open. The result builds on recent work placing bipartite matching in catalytic logspace and demonstrates the surprising power of reusing memory that must be returned untouched.
Catalytic computing is a close cousin of reversibility, since restoring borrowed space exactly is a reversibility constraint — making this a notable follow-up to the recent wave of catalytic-space breakthroughs.