MIAO/BARC talk by Ian Mertz

Tuesday, April 22, 2025, Ian Mertz, postdoc at Charles University in Prague, Czech Republic, will give a talk on "Catalytic Computing: A Primer".

Abstract:
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.

Bio:
Ian Mertz is a postdoctoral researcher in the Center for Foundations of Contemporary Computer Science (CZSI) group at Charles University with Michal Koucký. He did a bachelor's degree at Rutgers University with Eric Allender, a masters and Ph.D at University of Toronto with Toniann Pitassi, and a postdoc at University of Warwick with Igor Carboni Oliveira. His work is on computational complexity with a focus on catalytic computing, composition theorems, and space-bounded computation, along with other work on lifting and proof complexity.

Host:
Susanna Rezende