Catalytic Computing and Register Programs Beyond Log-Depth

In a seminal work, Buhrman et al. (STOC 2014) defined the class $CSPACE(s,c)$ of problems solvable in space s with an additional catalytic tape of size c, which is a tape whose initial content must be restored at the end of the computation. They showed that uniform TC¹ circuits are computable in catalytic logspace, i.e., CL=CSPACE(O(logn), 2^O(logn)), thus giving strong evidence that catalytic space gives L strict additional power. Their study focuses on an arithmetic model called register programs, which has been a focal point in development since then. Understanding $CL$ remains a major open problem, as TC¹ remains the most powerful containment to date. In this work, we study the power of catalytic space and register programs to compute circuits of larger depth. Using register programs, we show that for every ε > 0, SAC² ⊆ CSPACE(O(log²nloglogn), 2^O(log1+ε n)) This is an O(log log n) factor improvement on the free space needed to compute SAC², which can be accomplished with near-polynomial catalytic space. We also exhibit non-trivial register programs for matrix powering, which is a further step towards showing NC² ⊆ CL.