Can memory be useful even when it's already full? In the catalytic computing model (Buhrman et al. 2014), we consider a space bounded Turing machine with additional access to a much larger hard drive, with the caveat that the initial contents of this extra space must be restored after any computation. Despite this restriction, catalytic computation gains surprising power over ordinary space-bounded computation, even above and beyond resources such as randomness and non-determinism.

In this talk we will survey the field of catalytic computation. We will cover the base catalytic model and where it fits into traditional complexity theory; variants of the model, such as lossy, randomized, non-deterministic, and non-uniform catalytic computation; known techniques, such as register programs and compress-or-random approaches; applications of catalytic ideas to other settings; and potential directions for the future of the field.

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.