The $5000 Compression Challenge (2001)

No. You sound as if you’re familiar with the culture but it’s clear that you’re not.

The problem with comp.compression was always that its Eternal September is new people showing up every week claiming they’ve found a universal compression algorithm that compresses everything - the perpetual motion machine of information theory. Having gotten tired of explaining to people who think they’re fighting “dogma” not the laws of the universe, people start trying to find other ways to make them put up or shut up, so they could have some peace and quiet.

Like sending them a file full of RNG output and wait for them to realize this was their teachable moment.

Winning the challenge - without engaging in out of band bullshit (compressor + output should be the giveaway) doesn’t prove you have found a universal compression algorithm. It only proves the RNG is flawed. Which would be very interesting but not break Shannon.

The problem is compressor + file means “no out of band data” to a reasonable person and we have already established we are dealing with unreasonable people.

Not

> My main motivation was to "out-trick the tricker". I thought the chances of me making any money were very remote.

If they're trying to dissuade "universal compressors" then Mike needed to ask for the algorithm first, and then generate his file. If you tell me "I bet you can't compress this file!" then I can do whatever I want to write some stupid one-off compressor to shave a byte off and take your money.

I'm not saying 'Mike' had a high-effort ask, because clearly it wasn't particularly well thought out. Just that other people were glad for any Mike at all.

It's a limited risk. Even if the file is compressible by one byte, it's very unlikely you can figure out how to get a decompressor functioning without plenty of bytes of overhead. And even if that problem disappears, he'd still win 99.6% of the time.

And you can get rid of that risk by requiring 100 bytes of shrink. Just measure the size right.

I'm not familiar with the culture.

Nothing in the challenge says anything about doing universal compression. In fact the key point I'm trying to make is that you _don't_ have to make a universal compressor or break entropy to win, instead just find some scheme that makes 2% of random files shorter than the original, even if it makes 98% of files much much longer. The overall entropy is increased. I wouldn't use this for anything else. But it does beat the challenge as stated.

I'd agree that Patrick didn't follow the "spirit" of the challenge or do anything interesting with compression. But in doing this I think he made a good point, which is roughly that you need to be very careful and explicit when posing challenges like this or people are going to use your sloppy wording against you.

I think it would be better to require a meaningful percentage (say 1%) of compression rather than an exact count of bytes. Especially while people can ask for arbitrarily large files.

The chance that a randomly generated 1KB file can shrink by 100 bytes is the same as the chance that a randomly generated 100MB file can shrink by 100 bytes.

And that chance is too low to distinguish from zero before the universe dies.

> Nothing in the challenge says anything about doing universal compression

Because it’s out of context. It also makes the winner seem more sympathetic, which is why it’s not accident it’s not provided. It’s the Missing, Missing Reason.

As someone else said, if the reward was a million dollars then this becomes a game theory problem.

If you have $100 in disposable income it might be worth the lark if the officiant is uncareful with their chosen text. Though odds are good he pulled it from random.org. That’s where we used to send people.