Catalytic computation

Abstract

Catalytic computation was defined by Buhrman et al. (STOC, 2014). It addresses the question whether memory, that already stores some unknown data that should be preserved for later use, can be meaningfully used for computation. Buhrman et al. provide an intriguing answer to this question by giving examples where the occupied memory can be used to perform computation. In this expository article we survey what is known about this problem and how it relates to other problems.