| Title | : | Almost-Catalytic Computation |
| Speaker | : | Bhabya Deep Rai (IITM) |
| Details | : | Fri, 25 Aug, 2023 3:00 PM @ Turing Hall (SSB 334 |
| Abstract: | : | Catalytic Turing Machines (introduced by Buhrman et al (2014)) is a model which has a very small working space, while giving access to another large full space (called catalytic space) with arbitrary contents. This catalytic space can be used for computation, under the condition that the initial contents of this full space get restored at the end. The class CL is the set of languages computed by catalytic Turing machines equipped with O(log n) workspace and polynomial size catalytic space. Buhrman et al (2014) demonstrated the power of the model by proposing efficient algorithms for the reachability problem in this model. However, designing algorithms for the catalytic computation model is still a challenging task. With this view, we relax the original restoration requirement and study cases where we do not need to restore the content of the catalytic tape for all possible contents. If the content of the catalytic tape is w in A (called the catalytic set), then the catalytic Turing machine needs to restore it at the end of the computation, and it is not a requirement when w is not in the catalytic set. We call such machines almost-catalytic Turing machines.
We observe that to design catalytic algorithms for a problem, it suffices to design almost-catalytic algorithms for the problem where the catalytic set is the set of strings of odd weight (PARITY). Towards this, we consider two complexity measures of the set A which are maximized for PARITY. One is the random projection complexity (denoted by R(A)) and the other is the subcube partition complexity (denoted by P(A)). We show that, for all k ge 1, there exists a language A_k subseteq Sigma^* such that any Turing machine that uses space O(n^k) can be simulated by almost catalytic Turing machines that has random projection complexity of m/4 and exponentially large partition complexity. This is in contrast to the catalytic machine model where it is unclear if it can simulate Turing machines that uses even omega(log n) space. We further show improved simulations on these complexity parameters if we are simulating Turing machines that run in O(log^k n) space instead of O(n^k) space. Our main technical idea is that of using special logspace decodable codes to design almost catalytic algorithms. Finally, we explore limitations of a direct simulation via this approach, by demonstrating connections to parameters of linear codes. Enroute our study, we also demonstrate the power of an extra alphabet in the catalytic set by demonstrating that with an extra alphabet, the CL machines can simulate any polynomial space Turing machine as well. |
