Computing with Full Memory in 2026
Ian Mertz | Charles University
Catalytic computing, the study of using full memory as a resource in space-bounded computation, has seen a resurgence of interest in the past few years, with new techniques, such as the compress-or-random paradigm, as well as applications, most notably the breakthrough by Williams on time versus space. More recently, there has been an emerging algorithmic direction within the field as well, where the goal is to solve basic primitives, such as graph connectivity, in a time-space efficient manner by adding the power of catalytic memory. Furthermore, catalytic space as a resource has now been studied in various settings beyond the usual machine model, such as streaming and communication complexity.
We will survey such new directions in catalytic computing, with a focus on a few elementary algorithms which illustrate and exemplify these trends.
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
Location
- DC 1304
- Online on Zoom