4 ms·

Even without doing any filesystem tricks, the challenge seems quite possible. While it's true that writing a compressor that compresses all input data is imposs

Even without doing any filesystem tricks, the challenge seems quite possible. While it's true that writing a compressor that compresses all input data is impossible, this barrier is removed because the compressor only needs to work on a single file.

praptak 14y ago
But the "decompressor" here is also more or less fixed - it's the environment in which the challenger program needs to run. So, the organizer of the challenge would need to be unlucky to pick a file that is compressible for this particular decompressor. Mathematically this has non-zero (albeit very small) probability but I'd wager that even having such file it would be unfeasible to find its compressed form. Maybe the file is the third million of bytes of pi squared, but how do you find this fact?
UnoriginalGuy 14y ago
But you're forgetting what the challenge actually is. It is file+decompressor < input. So by the very nature of it if your decompressor is non-zero in length, you have to find some efficiency/tricks to make the file smaller. Realistically the overhead on the decompressor will be 10 KB and that is before any kind of actual logic, so you are looking at shaving a minimum of 50 KB off of the original file (which is completely random).
- algorias 14y ago
  I'm not forgetting that. It's just that any specific random file will have (with high probability), patterns that can be exploited. It's not guaranteed to work on all files of course. The theoretical limit (per bijection argument) is that at most half the strings of length n can be losslessly represented in strings of length n-1, because there are half as many strings of length n-1 than of length n. So if, for example, 2% of files can actually be reduced in size (I don't know what the actual number is, and if it is even computable) that's still positive EV in a $100 vs $5000 bet.
  - jgeralnik 14y ago
    The file is not really random, though, since Mike generated it and had time to make sure it was a "good" file before sending it on. That is, if the file was truly random, it would have a chance of 1/(2^X) of being all 0, where X is the size of the file. But since Mike would reject that file, the chance is actually 0. Same for all files with easily exploitable patterns - for example, I am sure that Goldman checked that the file could not be compressed with gzip before sending it. So the EV is probably not positive, even if there is a small chance that a random file of size X can be compressed.

praptak 14y ago

But the "decompressor" here is also more or less fixed - it's the environment in which the challenger program needs to run. So, the organizer of the challenge would need to be unlucky to pick a file that is compressible for this particular decompressor. Mathematically this has non-zero (albeit very small) probability but I'd wager that even having such file it would be unfeasible to find its compressed form. Maybe the file is the third million of bytes of pi squared, but how do you find this fact?

UnoriginalGuy 14y ago

But you're forgetting what the challenge actually is. It is file+decompressor < input. So by the very nature of it if your decompressor is non-zero in length, you have to find some efficiency/tricks to make the file smaller. Realistically the overhead on the decompressor will be 10 KB and that is before any kind of actual logic, so you are looking at shaving a minimum of 50 KB off of the original file (which is completely random).

algorias 14y ago
I'm not forgetting that. It's just that any specific random file will have (with high probability), patterns that can be exploited. It's not guaranteed to work on all files of course. The theoretical limit (per bijection argument) is that at most half the strings of length n can be losslessly represented in strings of length n-1, because there are half as many strings of length n-1 than of length n. So if, for example, 2% of files can actually be reduced in size (I don't know what the actual number is, and if it is even computable) that's still positive EV in a $100 vs $5000 bet.
- jgeralnik 14y ago
  The file is not really random, though, since Mike generated it and had time to make sure it was a "good" file before sending it on. That is, if the file was truly random, it would have a chance of 1/(2^X) of being all 0, where X is the size of the file. But since Mike would reject that file, the chance is actually 0. Same for all files with easily exploitable patterns - for example, I am sure that Goldman checked that the file could not be compressed with gzip before sending it. So the EV is probably not positive, even if there is a small chance that a random file of size X can be compressed.