I 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.
Aren't cryptographically secure PRNGs supposed to produce outputs indistinguishable from truly random numbers?
The $5000 Compression Challenge
121–130 of 175 posts
Re: The $5000 Compression Challenge
#122Re: The $5000 Compression Challenge
#123By the way in a theoretical sense Mike lost when he said he would allow multiple files and count their sizes: this is because [] is not the same as [[][][]], but consists of 3 empty sets. You can theoretically encode a file into just a bunch of 0-byte files, without using the order of the files or their names. He shouldn't have agreed to count only their sizes.
For the theoretical encoding into 0-sized files, you can simply interpret the input file as a binary number, and then create that many empty files.
This is not a practical solution of course - you can only compress two bytes down to 0-byte files this way, as 2^16-1 is already up to 65535 empty files. For three bytes it's up to 16,777,215 files.
If you wanted to store 9 bytes in unary as the number of empty files, you would need 2^72-1 = 4.7 sextillion (million quadrillion) files. Obviously that is not actually possible. But even 9 bytes is hardly enough to interpret the files as binary again. (Unless you can somehow get Mike to agree to the invocation - since the decompression program itself doesn't need to store any information and theoretically could be 0, 1 or 2 bytes.) But theoretically you don't need anything other than what Mike foolishly agreed to: allowing multiple output files counting their sizes.
2.
There is also another theoretical way to make money off of Mike, but it is not practical. (It doesn't work.) If we were not limited to bytes but could use bits, you could shave up to 5 bits off of every input file, if you figured out a way to decompress it by always prepending the bits 00000. (Theoretically there is only 1 pigeonhole to decompression, so you do not need to store any information in the decompression algorithm and it has no minimum size).
If Mike is using a random source for the files, this would result in a correct decompression in 1/32 of cases. But Mike is giving 49:1 odds (risk $100, get $5000), which is better than 31:1. So you could simply repeat the game with Mike thousands of times, always using the same decompression algorithm, until you have all of Mike's money. This works better if Mike is a computer, of course.
And it doesn't work at all on any actual systems, as a nibble is less than a byte and would not count as savings even if you could encode the decompression algorithm into a 0-byte (or up to 3 bit) invocation.
Re: The $5000 Compression Challenge
#124Earlier quoted context omitted.
what if instead of using your own dictionary, you use an index into an existing dictionary? such as an index into a subsequence of pi. Couldn't you then find a sequence of bytes in the file in which the index into pi takes less bytes and then replace them all with the index? If you couldn't find any in pi use e or another such number? What am I missing
In this case your dictionary either doesn't have everything or to adequately point to it you take as much space as not using it. While Pi has all pairs of 2 digits, your index would take more space than storing the pairs itself (because you might need to go beyond position 99) For one situation you might "get lucky" and find a coincidence, but this won't scale generically
I admit this fooled me for a bit. Good news is, I won't be fooled again by something similar :)
Re: The $5000 Compression Challenge
#125Why wouldn't binary run length encoding work here? E.g. "compressing" 11100110 to 30020 for example?
Re: The $5000 Compression Challenge
#126I absolutely believe Mike should have paid Patrick. On the simple premise that since Mike was hosting a bet that he KNEW was impossible (i.e. under no circumstance, ever, would he have to pay the 5000$), then literally the only point of the game is to find any loopholes. Otherwise it's just Mike preying on unsuspecting victims. If you design an impossible game, the only possible thing for anyone to do is to break it.…
That sounds close to cheating, but I think it's exactly in the spirit of both the original challenge by Mike and the response by Patrick. After all, the original challenge didn't mention multiple files (so it's not surprising that this limitation isn't mentioned), and the subsequent alteration to the rules was initiated by Patrick, who intentionally tried to inject a loophole, but failed to specify the need to keep the files in order. His rules; he should have to live by them.
Also, I suspect that if Patrick had mentioned the need to leave the file names unaltered or in order, there's a good chance that Mike would have smelled a rat. After all, it is precisely in that side-channel where the information gain is to be had.
Re: The $5000 Compression Challenge
#127A trick similar to the recursive Barf compressor (add information to the filename). http://mattmahoney.net/dc/barf.html A longer running challenge is http://www.drdobbs.com/architecture-and-design/the-enduring-... No entry fee, $100 prize, and just as unfair. A completely serious compression challenge with serious consequences for AI and NLP: http://prize.hutter1.net/ up to 50.000$ prize money, but severe restriction…
If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file? There is no such thing as random file . Randomness is not a property of a single file. You can't look at a byte sequence and say that "it's random". It can be random looking, you can run some statistic analysis on the byte sequence and say "It's probably generated by some good random algorithm", but even h…
Interestingly, this is less true than you might think. The mathematics of Kolmogorov complexity[1] formalizes the idea that a given finite fixed string is "random". In this framework, you can have a byte sequence that definitely is random. (However, your second sentence I quoted is still technically true here as well because it is algorithmically undecidable how random the string is.)
(In fact one of the definitions of a random string is one that is incompressible, i.e. there is no algorithm with shorter description than the string that produces the string.)
Re: The $5000 Compression Challenge
#128Mike Goldman originally wrote the challenge such that it calls for one file and one decompressor. However, when subsequently asked whether there can be multiple files, he agreed; thereby he was arguably duped. He didn't say "okay, but there will be a 256 byte size penalty per additional file", he just plainly agreed. This means that the original formula for adding the size of the solution applies: just the file sizes…
> He didn't say "okay, but there will be a 256 byte size penalty per additional file", he just plainly agreed. Exactly. IMO the challenge-setter is the one being more unfair here, since his metadata-based reason to reject the solution applies to submissions made under the original rules too. He accepted an amendment without counter-amending to cover that loophole, so if he stands by his word, he has to pay up. It cas…
Given the fact that Patrick made the rules concerning multiple files, and that they were intentionally tricky, I think it's fair to interpret them in that spirit - as a trick.
Notably, even without the ordering there is still some information leakage purely in terms of file sizes, but that's a little harder to exploit (likely still possible with a 3mb file). Of course, the rules don't explicitly state the directory must be otherwise empty...
Frankly, I think it's pretty reasonable that Patrick "lost" the bet, even if Mike reasoning wasn't sound. For Patrick to have won that bet would have required quite a list of requirements of how those "other" files were to be passed to the decompressor. Such requirements were not presented, and if they had been they would have been obviously fishy.
Re: The $5000 Compression Challenge
#129Earlier quoted context omitted.
It does use the filenames, for ordering. If you renamed the files so they sort differently, they would not decompress correctly.
We probably agree that any program should be allowed to uniquely identify the files making up the input data. And if Mike would have spotted the (other) more obvious loophole, which is to store input data in only the filenames, he could have given this (possibly the only) sensible answer: "Yes, multiple files whose summed up size + the size of the decompressor are smaller than the original file are ok. But the files…
Providing multiple files with the (deceptive) intention of storing data via filesystem metadata, but then failing to specify how filesystem metadata is to be treated is just asking for it.
Re: The $5000 Compression Challenge
#130I absolutely believe Mike should have paid Patrick. On the simple premise that since Mike was hosting a bet that he KNEW was impossible (i.e. under no circumstance, ever, would he have to pay the 5000$), then literally the only point of the game is to find any loopholes. Otherwise it's just Mike preying on unsuspecting victims. If you design an impossible game, the only possible thing for anyone to do is to break it.…
The purpose for the impossible game was to provide a distraction to people going to Usenet comp.compression and announcing their brilliant new algorithm and claiming it could compress any file better than any other algorithm.
Obnoxiousness just means this challenge becomes interesting to code-golfers who will also try to obey the rules but produce a broken result.