Title: The Structure of Catalytic Space: Capturing Randomness and Time via Compression
Speaker: Ian Mertz (Charles University, Prague)
Invited by: Bruno Loff (LASIGE, DM/FCUL)
When: January 15, 2025, 10:30-13:00
Where: FCUL, C6.2.33

Abstract: In the catalytic logspace (CL) model of (Buhrman et.~al.~STOC 2013), we are given a small work tape, and a larger “catalytic” tape that has an arbitrary initial configuration. We may edit the catalytic tape, but it must be exactly restored to its initial configuration at the completion of the computation. This model is of interest from a complexity-theoretic perspective as it gains surprising power over traditional space. However, many fundamental structural questions remain open. We substantially advance the understanding of the structure of CL, addressing several questions raised in prior work. Our main results are as follows.
1: We unconditionally derandomize catalytic logspace: CBPL=CL.
2: We show time and catalytic space bounds can be achieved separately if and only if they can be achieved simultaneously: any problem in CLP can be solved in polynomial time-bounded CL.
3: We characterize deterministic catalytic space by the intersection of randomness and time: CL is equivalent to polytime-bounded, zero-error randomized CL.

Our results center around the compress-or-random framework. For the second result, we introduce a simple yet novel compress-or-compute algorithm which, for any catalytic tape, either compresses the tape or quickly and successfully computes the function at hand. For our first result, we further introduce a compress-or-compress-or-random algorithm that combines runtime compression with a second compress-or-random algorithm, building on recent work on distinguish-to-predict transformations and pseudorandom generators with small-space deterministic reconstruction.
This is joint work with James Cook, Jiatu Li, and Edward Pyne.

Bio: I’m a postdoctoral researcher in the Center for Foundations of Contemporary Computer Science (CZSI) group at Charles University, where I’m fortunate to be working with Michal Koucký. Before this I was a postdoc at at University of Warwick under Igor Carboni Oliveira, before that I was a graduate student at University of Toronto advised by Toniann Pitassi, and even further back I was an undergraduate at Rutgers University. At the moment my research interests mostly include catalytic computing, composition theorems, and space-bounded computation, along with some work on lifting and proof complexity.

This presentation is supported by the project HOFGA, Grant agreement ID: 101041696, funded by European Reserach Council’s Horizon Europe programme.