The $5000 Compression Challenge • Hacker News Board

Re: The $5000 Compression Challenge

#111

Post by jakobegger » Sun, Mar 08, 2015, 9:52 AM UTC

compbio wrote: post #38

A 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…

Bruteforcing a solution until hashes match doesn't work. If you try to bruteforce X bits and use a hash of size Y for validation, you will get 2^(X-Y) possible solutions.

(I made the same mistake some time ago when I tried to bruteforce a 4 byte RC4 key with 3 known bytes in the plain text; I found 256 solutions.)

Re: The $5000 Compression Challenge

#112

Post by cnvogel » Sun, Mar 08, 2015, 9:58 AM UTC

anamexis wrote: post #89

caf wrote: post #88

Earlier quoted context omitted.

In fact this solution doesn't use either the number of files or their filenames to encode additional information - it uses the sizes of those files to encode the additional information.

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 must be uniquely named inputfile.0 ... inputfile.NNN." Which is exactly what Patrick delivered.

Re: The $5000 Compression Challenge

#113

Post by yummybear » Sun, Mar 08, 2015, 10:03 AM UTC

I remember a "fractal compression" hoax one time. It would compress a file ridiculously (like 1 1mb file down to 100 bytes), and decompress it flawlessly. Of course it just moved the file to some other place on the harddrive and created a "compressed file" full of junk and restored the file on decompress. Good one...

Re: The $5000 Compression Challenge

#114

Post by cnvogel » Sun, Mar 08, 2015, 10:04 AM UTC

Dylan16807 wrote: post #32

barrkel wrote: post #30

Earlier quoted context omitted.

The EOF is not at a cost of zero bytes; it costs as much as storing the length of each constituent file. The extra space used is in the file system accounting.

It's at a cost of 0 competition score bytes. Mike screwed up by allowing an alphabet of 257 symbols and then only counting 256 of them. Pretty much any compression or repacking algorithm could have been used at that point.

Dylan16807, that's a very concise way to put it, thanks for making that comment.

Re: The $5000 Compression Challenge

#115

Post by zik » Sun, Mar 08, 2015, 10:33 AM UTC

x0x0 wrote: post #91

snowwrestler wrote: post #42

The point of the challenge was to tempt people who do not understand compression as well as Mike into putting themselves into a position for Mike to mock and/or shame them. From that respect, it seems to me like it was a trick. In my experience, people who set up such tricks do not usually respond well when the tables are turned. There are some people in the world who take it personally when other people don't unders…

Why do you think that rather than Mike is genuinely interested in novel compression methodologies, and willing to pay some money to make interested people attempt to discover them?

Because information theory says it's impossible.

Re: The $5000 Compression Challenge

#116

Post by DanBC » Sun, Mar 08, 2015, 10:37 AM UTC

compbio wrote: post #38

A 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…

> Why does he want exactly his own random file?

He's running a model and needs to use the same random data each time.

Re: The $5000 Compression Challenge

#117

Post by DanBC » Sun, Mar 08, 2015, 10:45 AM UTC

prettyrandom100 wrote: post #96

I didn't see anything that mentions run-time in the challenge. I think a good compression challenge should mention about run-time. Theoretically, it would be possible to hash parts of the file and then brute force the hash in the decompressor. This would take a lot of time but would work.

Hashes suffer from the same pigeonhole problem as compressed data.

Re: The $5000 Compression Challenge

#118

Post by sjwright » Sun, Mar 08, 2015, 10:48 AM UTC

paulsecwhatt wrote: post #95

I 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.…

> If you design an impossible game, the only possible thing for anyone to do is to break it.

Which is the Kobayashi Maru in a nutshell. In that fictional case, Kirk was disqualified but also received a commendation.

Re: The $5000 Compression Challenge

#119

Post by xorcist » Sun, Mar 08, 2015, 10:51 AM UTC

fishnchips wrote: post #106

I am actually surprised that Patrick did not compress the original data to 0 bytes by keeping all the data in filenames. That would be the ultimate troll ;)

I disagree. You could legitimately say he just stored the data in the metadata fields. But files have a size, even as a stream, completely regardless of metadata. I think this is a more clever hack.

Re: The $5000 Compression Challenge

#120

Post by DanBC » Sun, Mar 08, 2015, 10:53 AM UTC

x0x0 wrote: post #91

snowwrestler wrote: post #42

The point of the challenge was to tempt people who do not understand compression as well as Mike into putting themselves into a position for Mike to mock and/or shame them. From that respect, it seems to me like it was a trick. In my experience, people who set up such tricks do not usually respond well when the tables are turned. There are some people in the world who take it personally when other people don't unders…

Why do you think that rather than Mike is genuinely interested in novel compression methodologies, and willing to pay some money to make interested people attempt to discover them?

There was a problem in comp.compression (or whatever Usenet newsgroup) of arrogant challengers announcing their brilliant new compression algorithm. This bet is a way of demonstrating at least the pigeon hole problem to other people.