Space: Connecting Catalytic And Classical Approaches
Space: Connecting Catalytic And Classical Approaches
How useful is already-filled space? Catalytic space is a new model of space-bounded computation where a small worktape is augmented by a larger "catalytic" tape, that can be edited but must be restored at the end of the computation.Â
The goal of this workshop is to get participants to the research frontier in catalytic computing, to identify open problems that seem promising, and to create connections between catalytic space and other fields. We hope you will join us!
Some recent ideas that we want to explain (and start building on) are:
Bipartite matching is in catalytic logspace [AM FOCS25]
Fast catalytic algorithms for graph connectivity [CP ITCS26]
Nondeterminism and randomness do not give catalytic space more power [KMPS FOCS25]