“Obviously” is a dangerous word, even in scenarios that seem simple. Suppose, for instance, you need to do an important computation. You get to choose between two computers that are almost identical, except that one has an extra hard drive full of precious family photos. It’s natural to assume that the two options are equally good — that an extra drive with no space remaining won’t aid your computation.
“Obviously, it doesn’t help, right?” said Bruno Loff (opens a new tab), a computer scientist at the University of Lisbon.
Wrong. In 2014, Loff and four other researchers discovered that adding full storage space can in principle make computers more powerful. Their theoretical framework, called catalytic computing (opens a new tab), has become an object of study in its own right. And recently, it also helped researchers prove a startling result (opens a new tab) in a related area of computer science: The standard approach to resolving a major open question about the role of memory in computation is most likely a dead end.
“It’s quite a feat,” said Pierre McKenzie (opens a new tab), a complexity theorist at the University of Montreal. “I really appreciate these results.”
To read more, click here.