Please note: This seminar will take place in DC 1304 and online.

Ian Mertz, Postdoctoral researcher
Computer Science Institute
Faculty of Mathematics and Physics, 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.

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.

To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.