Hacker News Reader

Comment by tippytippytango | Hacker News Reader

If I give you a hard drive full of photos, you could compress them, use the excess hard drive space for your algorithm, then uncompress the photos and give a full hard drive back to me. Is that’s what’s going on here?

Basically it’s exploiting unused channel capacity of the memory if the Shannon entropy isn’t maxed out?

View on HN

They are explicitly not assuming anything about the content of the auxiliary space (full hard drive).

So the data might be incompressible and thus compressing it and restoring it afterwards would not work.

Edit: From the paper:

> One natural approach is to compress the data on the hard disk as much as possible, use the freed-up space for your computation and finally uncompress the data, restoring it to its original setting. But suppose that the data is not compressible. In other words, your scheme has to always work no matter the contents of the hard drive. Can you still make good use of this additional space?

Why wouldn't decompressing work? The whole point is that the hard drive is restored to its (arbitrary) original state upon completion.

Some data is just incompressible, like random numbers, encrypted data or already compressed data.

The compression from GP's comment is irrelevant.

Put arbitrary data in, get the same arbitrary data out.

it is indeed one of important techniques in catalyitic computing that either 1)you can compress the catalyst, giving you space or 2)uncompressible catalyst gives you a source of randomness

Reply on news.ycombinator.com