{"id":14575,"date":"2025-03-30T11:05:48","date_gmt":"2025-03-30T11:05:48","guid":{"rendered":"https:\/\/topat10.com\/?p=14575"},"modified":"2025-03-30T11:05:48","modified_gmt":"2025-03-30T11:05:48","slug":"why-adding-a-full-hard-drive-can-make-a-computer-more-powerful","status":"publish","type":"post","link":"https:\/\/topat10.com\/?p=14575","title":{"rendered":"Why Adding a Full Hard Drive Can Make a Computer More Powerful"},"content":{"rendered":"


\n<\/p>\n

\n

Those are pretty stringent constraints, so it wasn\u2019t obvious that the extra memory could ever prove useful. But to their surprise, Buhrman and Cleve showed that if you tweak bits in just the right way, you really can get extra computational oomph out of a full memory.<\/p>\n

\u201cThat was a shocker for everyone,\u201d said Loff, who was a graduate student in Buhrman\u2019s group at the time, working on the memory question with his fellow student Florian Speelman<\/a>. The team soon extended the result to an even larger class of problems, and published their combined results<\/a> in 2014.<\/p>\n

They named the new framework catalytic computing, borrowing a term from chemistry. \u201cWithout the catalyst, the reaction would not have proceeded,\u201d said Raghunath Tewari<\/a>, a complexity theorist at the Indian Institute of Technology, Kanpur. \u201cBut the catalyst itself remains unchanged.\u201d<\/p>\n

Not Far From the Tree<\/h2>\n

A small band of researchers continued to develop catalytic computing further, but no one even tried to apply it to the tree evaluation problem that had initially inspired Kouck\u00fd\u2019s quest. For that problem, the remaining open question was whether a small amount of memory could be used for storage and computation simultaneously. But the techniques of catalytic computing relied on the extra, full memory being very large. Shrink that memory and the techniques no longer work.<\/p>\n

Still, one young researcher couldn\u2019t help wondering whether there was a way to adapt those techniques to reuse memory in a tree evaluation algorithm. His name was James Cook<\/a>, and for him the tree evaluation problem was personal: Stephen Cook, the legendary complexity theorist who invented it, is his father. James had even worked on it in graduate school, though he mostly focused on completely unrelated subjects<\/a>. By the time he encountered the original catalytic computing paper in 2014, James was about to graduate and leave academia for software engineering. But even as he settled into his new job, he kept thinking about catalytic computing.<\/p>\n

\u201cI had to understand it and see what could be done,\u201d he said.<\/p>\n

For years, James Cook tinkered with a catalytic approach to the tree evaluation problem in his spare time. He gave a talk about his progress at a 2019 symposium in honor of his father\u2019s groundbreaking work<\/a> in complexity theory. After the talk, he was approached by a graduate student named Ian Mertz<\/a>, who\u2019d fallen in love with catalytic computing five years earlier after learning about it as an impressionable young undergrad.<\/p>\n

\u201cIt was like a baby bird imprinting scenario,\u201d Mertz said.<\/p>\n

\n
\n