EVENT

Event News

Talk on "Collapsing catalytic classes" by Prof. Michal Koucky

We are pleased to inform you about the upcoming seminar by Prof. Michal Koucky titled:"Collapsing catalytic classes" Everyone interested is cordially invited to attend!

Title:

Collapsing catalytic classes

Abstract:

A catalytic machine is a space-bounded Turing machine with additional access to a second, much larger work tape, with the caveat that this tape is full, and its contents must be preserved by the computation. Catalytic machines were defined by Buhrman et al. (STOC 2014), who, alongside many follow-up works, exhibited the power of catalytic space (CSPACE) and in particular catalytic logspace machines (CL) beyond that of traditional space-bounded machines.

Several variants of CL have been proposed, including non-deterministic and co-non-deterministic catalytic computation by Buhrman et al. (STACS 2016) and randomized catalytic computation by Datta et al. (CSR 2020). These and other works proposed several questions, such as catalytic analogues of the theorems of Savitch and Immerman and Szelepcsényi. Catalytic computation was recently derandomized by Cook et al. (STOC 2025), but only in certain parameter regimes.

We settle almost all questions regarding randomized and non-deterministic catalytic computation, by giving an optimal reduction from catalytic space with additional resources to the corresponding non-catalytic space classes. With regards to non-determinism, our main result is that CL=CNL and with regards to randomness we show CL=CPrL where CPrL denotes randomized catalytic logspace where the accepting probability can be arbitrarily close to 1/2. In this talk I will explain the model, the results and give overview of the techniques.

Joint work with Ian Mertz, Edward Pyne and Sasha Sami.

Speaker:

Michal Koucky is a member of the Computer Science Institute of Charles University in Prague which is a part of the Faculty of Mathematics and Physics.
He is interested in theoretical computer science, especially in computational complexity, data structures, algorithms, and combinatorics. His last large projects are include the EPAC project supported by GA CR, and the LBCAD project funded by ERC.