The $5000 Compression Challenge • Hacker News Board

Re: The $5000 Compression Challenge

#31

Post by martinko » Sun, Mar 08, 2015, 2:53 AM UTC

davmre wrote: post #16

bagels wrote: post #10

Earlier quoted context omitted.

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.

Yes, but you don't get to see the file until after you've sent in the $100. So in order for this to be a good bet, you'd need a method that can compress a random file with at least 2% ($100/5000) probability. That's still quite difficult. An example of an algorithm that does compress 2% (actually 1/32 ~= 3%) of random files: just drop the initial five bits of the file, and replace them with zeros upon decompression.…

>you'd need a method that can compress a random file with at least 2% ($100/5000) probability

No, you'd need to be able to create a custom algo for that file with that probability. Quite a difference.

Re: The $5000 Compression Challenge

#32

Post by Dylan16807 » Sun, Mar 08, 2015, 2:54 AM UTC

barrkel wrote: post #30

nothrabannosir wrote: post #14

Quote from Mike: > Rather, you simply split the file into 218 parts ending with the > character "5" and then stripped that final character from each part. Thus the > "decompressor" is nothing more than a reassembler, > concatenating the parts and reappending > the character "5" after each. Well, that's exactly the definition of lossless compression. Look at e.g. how js crunch works: you create a dictionary of common…

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.

Re: The $5000 Compression Challenge

#33

Post by TillE » Sun, Mar 08, 2015, 2:59 AM UTC

In theory, I quite like the solution mentioned in the earlier threads: request a file that's a few kilobytes, then get two or three different hashes of the file, and write a "decompressor" that generates random files and checks the hashes.

It's just a shame that the heat death of the universe will probably occur before your program finishes.

Re: The $5000 Compression Challenge

#34

Post by skatenerd » Sun, Mar 08, 2015, 3:03 AM UTC

Can't he just send you a Kolmogorov-random file? The definition of randomness (in Kolmogorov sense) basically corresponds directly to his challenge.

Also, Kolmogorov-random sequences vastly outnumber non-random sequences in general, so with a long-enough file, I wonder how certain he can be that he has generated such a file.

http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...

Re: The $5000 Compression Challenge

#35

Post by Dylan16807 » Sun, Mar 08, 2015, 3:04 AM UTC

thomasahle wrote: post #29

AFAIK, information theory requires the _Expected_ size of a 'compressed' file be at least as large as the original. So we could create an encoding that compressed N/50 of the strings with lg(N/50)=lg(N)-lg(50) bits. That would save us lg(50) > 5 bits with 2% chance. In this game we have 50 tries (5000$/100$) so we'd be pretty sure to win. The correct price for this game is probably closer to 200$.

The problem is that even the most trivial linux-compatible decompressor will add a few bytes, and there's almost no chance of saving that many bytes. But sure it wouldn't hurt to require it be 100+ bytes smaller.

Re: The $5000 Compression Challenge

#36

Post by piannucci » Sun, Mar 08, 2015, 3:06 AM UTC

TillE wrote: post #33

In theory, I quite like the solution mentioned in the earlier threads: request a file that's a few kilobytes, then get two or three different hashes of the file, and write a "decompressor" that generates random files and checks the hashes. It's just a shame that the heat death of the universe will probably occur before your program finishes.

Sorry, but no. There are far more files with a given hash than just the one, if the file is longer than the hash. And having multiple hashes doesn't help until the hashes exceed the length of the file.

Re: The $5000 Compression Challenge

#37

Post by hyperpallium » Sun, Mar 08, 2015, 3:07 AM UTC

The file ordering contains information (done with filenames, comp.$i, but could use other file metadata).

Mike can escape his unthinking agreement to multiple files by the rules forbidding information in filenames.

Re: The $5000 Compression Challenge

#38

Post by compbio » Sun, Mar 08, 2015, 3:09 AM UTC

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 restrictions on memory and running time.

You can not beat Goldman's troll-ish challenge (certainly if the rules are retro-actively clarified in favor of the organizer). You could however try to put the challenge in limbo by creating a decompressor which bruteforces a solution, 'till some hashes match or the final heat death of the universe or the halting problem is solved, whichever comes first. Goldman will not be able to ever verify your solution, and when he does (theoretically it is not impossible), it means you win.

Or, instead of above Schrödinger's Compressor you can send a good random number generator back as your solution. If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file? Why does he want to do a diff between two random files, is he perhaps looking for order where there is none? But that's the same foolishness he accuses his participants of.

Re: The $5000 Compression Challenge

#39

Post by phamilton » Sun, Mar 08, 2015, 3:34 AM UTC

davmre wrote: post #16

bagels wrote: post #10

Earlier quoted context omitted.

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.

Yes, but you don't get to see the file until after you've sent in the $100. So in order for this to be a good bet, you'd need a method that can compress a random file with at least 2% ($100/5000) probability. That's still quite difficult. An example of an algorithm that does compress 2% (actually 1/32 ~= 3%) of random files: just drop the initial five bits of the file, and replace them with zeros upon decompression.…

Continuing that logic:

You could get 6% if you can also do the same on the end of the file. There's a 1 in 16 chance that any random sequence of data will start or end with 5 zeros. The same trick could be done for 1s to bring it up to 12%. In other words, 12% of sequences will either begin or end with 5 ones or 5 zeros.

Since you can inspect the data before writing the decompressor, if we can figure out how to pad the beginning or end of a byte sequence with five 1s or five 0s in 5 bytes or less, then your expected outcome is $625 (minus $100 to play). Using 6 bytes would give you an expected outcome of $312.5, 7 bytes would give you an expected outcome of $156.

7*'0'+a

That's 7 bytes. It's not really a executable decompressor, but it does capture the necessary steps required to decompress.

Re: The $5000 Compression Challenge

#40

Post by mappu » Sun, Mar 08, 2015, 3:43 AM UTC

skatenerd wrote: post #34

Can't he just send you a Kolmogorov-random file? The definition of randomness (in Kolmogorov sense) basically corresponds directly to his challenge. Also, Kolmogorov-random sequences vastly outnumber non-random sequences in general, so with a long-enough file, I wonder how certain he can be that he has generated such a file. http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...

How do you determine whether the file is kolmogorov-random?

The only approach is to try a perfect kolmogorov compressor, which doesn't exist (well, excepting brute force over the space of possible turing machines).