Catalytic memory is the new term for a method of computing whereby the computer carries out a computation using memory that it is already filled with data, returning it to its original state after use. The result is counter intuitive and was conjectured to be impossible.
In an article by CWI researchers Harry Buhrman, Bruno Loff and Florian Speelman, in collaboration with Richard Cleve (University of Waterloo, Canada) and Michal, Koucký (Charles University, Prague), it is demonstrated not only that this is possible, but also that this gives rise to a new complexity class and a new way of thinking about memory use with some applications to cryptography.
An extensive review of the results are discussed in the well known weblog from Richard Lipton on theoretical computer science. The article was presented this month at the prestigious ACM Symposium on the Theory of Computing (STOC).
Source: UvA/CWI
