Harry Buhrman in the news with new method of computation

Catalytic memory is the new term for a method of computation 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 a article by Harry Buhrman (UvA, CWI), Richard Cleve (University of Waterloo), Michal, Koucký (Charles University Prague), Bruno Loff (CWI) en Florian Speelman (CWI), 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.

The article was presented last week at the prestigious ACM Symposium on the Theory of Computing (STOC). An extensive review of the results are discussed in the well known weblog on theoretical computer science: http://rjlipton.wordpress.com/2014/06/01/how-to-avoid-leaving-clues/.

For more information, email buhrman at cwi.nl