Title:Bipartite Matching is in Catalytic Logspace
Speaker: Ian Mertz (Charles University, Prague)
Invited by: Bruno Loff (LASIGE, DM/FCUL)
When: January 21, 2026, 14:00-16:00
Where: FCUL, C6.2.33

Abstract: 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 can be computed in catalytic logspace with a polynomial time bound. Moreover, we show that can be reduced to the lossy coding problem for NC circuits. This has consequences for matching, catalytic space, and derandomization. Joint work with Aryan Agarwala.

Bio: I’m a postdoctoral researcher in the Center for Foundations of Contemporary Computer Science (CZSI) group at Charles University, where I’m fortunate to be working with Michal Koucký. Before this I was a postdoc at at University of Warwick under Igor Carboni Oliveira, before that I was a graduate student at University of Toronto advised by Toniann Pitassi, and even further back I was an undergraduate at Rutgers University. At the moment my research interests mostly include catalytic computing, composition theorems, and space-bounded computation, along with some work on lifting and proof complexity.

This presentation is supported by the project HOFGA, Grant agreement ID: 101041696, funded by European Reserach Council’s Horizon Europe programme.