A BORROWED FULL DISK MAKES COMPUTERS FASTER
Some problems are cheap in time but greedy in memory, others the reverse. For a few basic tasks, theorists have proved hard limits on the trade-off: with a small working memory, you cannot be fast. A new paper shows that a strange resource, a memory that is already full and must be returned intact, breaks those limits.
The borrowed hard drive
The model is called catalytic computing, introduced in 2014 by Buhrman, Cleve, Koucký, Loff and Speelman. An algorithm gets a tiny clean memory, on the order of log n bits for an input of size n, plus a huge dirty memory already filled with arbitrary data it did not choose. It may use both however it likes, but when it stops, every bit of the dirty memory must be exactly as it was.
The authors use the standard image: you borrow a friend’s enormous hard drive, full of precious digital memories, to run a computation. You do not want to lose a friend, so you restore every bit when done.
The model was first meant to prove that such memory is useless. Intuitively, to restore everything you must keep all the information, so you never free any room. Surprisingly, the opposite turned out to be true: full memory lets you solve problems nobody knows how to solve with clean memory alone. But those results were about space, and the algorithms were extremely slow.
Faster than what is provably possible
Adelmo Morrison Orozco, Nathan Sheffield and Ryan Williams (MIT) now look at speed. With logarithmic clean memory and a polynomial amount of borrowed memory, they give algorithms that:
- sort a list and compute a discrete Fourier transform in time n^(1+o(1)), almost linear;
- multiply matrices in time n^(ω+o(1)), as fast as the best known method with unlimited memory.
Without the borrowed disk, it is proven that the product of time and memory must be at least of order n² for sorting and the Fourier transform, and n³ for matrix multiplication. So these catalytic algorithms reach speeds that no ordinary small-memory algorithm can reach. The authors call it the first unconditional demonstration that catalytic algorithms outperform their non-catalytic counterparts.
Toggle, read, undo
The key ingredient is a short combinatorial trick. Suppose an algorithm can switch a section of the borrowed memory between an unknown value τ and τ + x, where x is the result it cares about. In a large “helper” table, also borrowed, add 1 to a carefully chosen set of entries. The entry at position τ goes up by one if and only if x belongs to a given set. Then run every step backwards, and the disk is as before, except for the bit of answer you wanted.
Stacking this trick layer by layer evaluates shallow circuits quickly. The authors then recast sorting networks, fast Fourier transforms and fast matrix multiplication as such circuits. For arithmetic, only the layers that multiply two unknowns cost extra; purely linear layers come almost free.
A fair comparison
One objection: the classic limits assume the answer is written once, from left to right, on a separate output tape, while catalytic algorithms write their answer into the borrowed disk. The paper addresses it. The authors show that their algorithms can write the answer in two passes over an output tape, and that for ordinary algorithms two passes help no more than one. The limits therefore still apply, and the separation holds. They also prove that one pass is not enough even with the borrowed disk: sorting then hits the same n² barrier.
A long list of beneficiaries
The same tools give fast catalytic algorithms for multiplying large integers and polynomials, counting triangles and finding cliques in networks, detecting paths and cycles, and matching text patterns with wildcards. Their running times match, up to small factors, the best known algorithms that have all the memory they want. In each case the borrowed memory must still come back exactly as it was lent.