Space and time are the two most foundational resources in the study of computation. However, they behave in very different ways that can make our intuitions fail. One key difference is that space, once it has been used for one purpose, can be erased and reused for another, while time spent is gone forever. Just ten years ago, Buhrman et al. discovered a shocking fact: even memory which is completely full can be reused, without erasure, for unrelated purposes. Inspired by chemistry, they defined catalytic space as memory which aids a computation without being altered by the process.
In this talk, we introduce the field of catalytic computation, from its inception to the recent explosion of results in the past few years. We will give an overview of the major techniques for using full memory as well as its greatest successes, including a novel relationship between space and time. Finally, we reflect on how re-using full memory forces us to reconsider our understanding of space.
Short Bio:
Ian Mertz is a postdoctoral researcher at the Computer Science Institute (IUUK) at Charles University in Prague. His work revolves around catalytic computing, a branch of space-bounded algorithms dealing with the use of full memory as a computational resource, as well as the study of how the complexity of problems compose over many instances. He received a B.Sc./B.A. from Rutgers University in 2016, an M.Sc. from University of Toronto in 2018, and a Ph.D. in computer science from University of Toronto in 2022, and has since held positions at University of Warwick and Charles University
