The $5000 Compression Challenge
patrickcraig.co.uk
The $5000 Compression Challenge
1–10 of 175 posts
Re: The $5000 Compression Challenge
#2yeah, he should have been smart enough to spot what was coming when he was asked about multiple files... or at least asked some more directed questions than 'what do you think you have that will solve this problem'
Re: The $5000 Compression Challenge
#3I think Patrick sums it up quite well. Perhaps the interesting thing is imagining how this would go down 15 years later in 2015: Patrick asks if the bet is available; it is. They enter into a 2-of-3 bitcoin transaction with 3rd-party escrow. Patrick and Mike sign the terms (probably written in pseudocode or python) using their sending bitcoin addresses (or GPG keys). Filesharing is an order-of-magnitude easier than setting up FTPs with personal IP addresses. The bet is promptly won by Patrick.
Ah, how things have changed in 14 years
Re: The $5000 Compression Challenge
#4I think Patrick sums it up quite well. Perhaps the interesting thing is imagining how this would go down 15 years later in 2015: Patrick asks if the bet is available; it is. They enter into a 2-of-3 bitcoin transaction with 3rd-party escrow. Patrick and Mike sign the terms (probably written in pseudocode or python) using their sending bitcoin addresses (or GPG keys). Filesharing is an order-of-magnitude easier than s…
They could have used an escrow service 15 years ago and the challenge terms could have been defined as a Python program since Python is 24 years old.
Re: The $5000 Compression Challenge
#5>It's not my fault that a file system uses up more space storing the same amount of data in two files rather than a single file.
Even without a filesystem - just sending data over the wire - you have to be able to delimit files in some way, and there's going to be overhead associated with that.
Another way to think of this is that any particular volume could be viewed as a single big file. How much space in that big file is he taking up?
Re: The $5000 Compression Challenge
#6I don't think it is 100% foolproof, even if no filesystem trickery is used. The random number generator used is likely not perfect and so the data should be compressible. I mean it would probably be quite difficult, but maybe possible.
Re: The $5000 Compression Challenge
#7See also section [9] of the comp.compression FAQ for more on the history of compression of random data:
Re: The $5000 Compression Challenge
#8I don't think it is 100% foolproof, even if no filesystem trickery is used. The random number generator used is likely not perfect and so the data should be compressible. I mean it would probably be quite difficult, but maybe possible.
From the link I posted in my other comment, a thought experiment... Yes, some random files can be compressed by a given program, but not all random files. The proof is fairly simple, once you think it through:
Theorem: No program can compress without loss all files of size >= N bits, for any given integer N >= 0.
Proof: Assume that the program can compress without loss all files of size >= N bits. Compress with this program all the 2^N files which have exactly N bits. All compressed files have at most N-1 bits, so there are at most (2^N)-1 different compressed files [2^(N-1) files of size N-1, 2^(N-2) of size N-2, and so on, down to 1 file of size 0]. So at least two different input files must compress to the same output file. Hence the compression program cannot be lossless.
Re: The $5000 Compression Challenge
#9Mike Goldman is now immortalized on the internet as someone who welches on bets...
Re: The $5000 Compression Challenge
#10I don't think it is 100% foolproof, even if no filesystem trickery is used. The random number generator used is likely not perfect and so the data should be compressible. I mean it would probably be quite difficult, but maybe possible.
From the link I posted in my other comment, a thought experiment... Yes, some random files can be compressed by a given program, but not all random files. The proof is fairly simple, once you think it through: Theorem: No program can compress without loss all files of size >= N bits, for any given integer N >= 0. Proof: Assume that the program can compress without loss all files of size >= N bits. Compress with this…
The challenge was to provide a decompressor for one file, not any or all files.
This proof of the impossibility of a compressor that can compress any file has been known for decades.