Catalytic Computing: A Primer

Can memory be useful even when it's already full? In the catalytic computing model (Buhrman et al. 2014), we consider a space bounded Turing machine with additional access to a much larger hard drive, with the caveat that the initial contents of this extra space must be restored after any computation. Despite this restriction, catalytic computation gains surprising power over ordinary space-bounded computation, even above and beyond resources such as randomness and non-determinism.

In this talk we will survey the field of catalytic computation. We will cover the base catalytic model and where it fits into traditional complexity theory; variants of the model, such as lossy, randomized, non-deterministic, and non-uniform catalytic computation; known techniques, such as register programs and compress-or-random approaches; applications of catalytic ideas to other settings; and potential directions for the future of the field.