3 papers
cs.DS2026
Catalytic Tree Evaluation From Matching Vectors
Alexandra Henzinger, Edward Pyne, Seyoon Ragavan
We give new algorithms for tree evaluation (S. Cook et al. TOCT 2012) in the catalytic-computing model (Buhrman et al. STOC 2014). Two existing approaches aim to solve tree evaluat…
cs.CC2025
The Structure of In-Place Space-Bounded Computation
James Cook, Surendra Ghentiyala, Ian Mertz +2
In the standard model of computing multi-output functions in logspace (), we are given a read-only tape holding and a logarithmic length worktape, and must print $…
cs.CC2025
Collapsing Catalytic Classes
Michal Koucký, Ian Mertz, Edward Pyne +1
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 pr…