2 papers
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.DS2025
Efficient Catalytic Graph Algorithms
James Cook, Edward Pyne
We give fast, simple, and implementable catalytic logspace algorithms for two fundamental graph problems. First, a randomized catalytic algorithm for connectivity running…