Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The $5000 Compression Challenge

patrickcraig.co.uk

Post reply on HN
Print view View original

81–90 of 175 posts

Re: The $5000 Compression Challenge

#81

Post by bo1024 »

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…

> A longer running challenge is http://www.drdobbs.com/architecture-and-design/the-enduring-.... No entry fee, $100 prize, and just as unfair.

At the 10-year scale, a whole new set of tricks opens up. Invent a sufficiently popular programming language, or contribute a lot to the linux kernel, and start surreptitiously hiding bits of the file on his OS (the easiest would be for you language to have a builtin function that spits out a small part of the file).

Re: The $5000 Compression Challenge

#82

Post by function_seven »

Intermernet wrote: post #69

Does the decompressor have to be wholly hosted locally? Could it just be a shim that pulls a more complex program from the net? There are grey areas here. Does a decompressor that depends on linked libraries count? Do things like libc count towards the total decompressor size? I know this was written 14 years ago, but we had the net then, and shared libraries aren't exactly a new thing. Where do you draw the line? Ca…

> Does the decompressor have to be wholly hosted locally? Could it just be a shim that pulls a more complex program from the net?

The judge can disconnect his computer from the Internet, attempt to run the submitted decompressor and file, and declare failure when it doesn't work. Nothing in the challenge guarantees Internet connectivity on the machine.

> Does a decompressor that depends on linked libraries count? Do things like libc count towards the total decompressor size?

Nope. In the email exchange, Mike said that just a script that called out to gunzip would be fine, and that he'd only count the size of the script as the decompressor size

> Where do you draw the line? Can any decompression code call an external dependency and not be disqualified in the same way?

Yup, as long as the dependency is already on the machine I suppose.

That's what's so enlightening about this challenge. Even a tiny, tiny script that calls to other programs still can't compress a "pathologically" random file by more than a few bytes.

Re: The $5000 Compression Challenge

#83

Post by eridius »

seandougall wrote: post #77
eridius wrote: post #72

Earlier quoted context omitted.

I admit I'm surprised to see this comment is still the top comment. I wrote it off when it was first written as being far too pedantic to be at all meaningful, but I guess other people are falling for the same trick. This is pure pedantry, and it's bad pedantry at that. Your argument is that Mike agreed that multiple files could be submitted, and from that you're drawing the completely baseless conclusion that the mu…

> completely baseless conclusion that the multiple files would be considered purely based on their file size You mean, like... > I meant can I send you a compressor and several compressed files whose total file size is less than the original uncompressed file and from which I can regenerate the original uncompressed file. (to which Mike agreed)?

Since this is still a pedantry argument: Mike agreed that Patrick could send multiple files, but Mike never agreed that these files would be accepted as a winning submission. Furthermore, Mike never agreed that the filenames of the files would be considered to be meaningful data (without contributing to the filesize calculation).

Re: The $5000 Compression Challenge

#84

Post by dvirsky »

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.

You could maybe use something like pi-fs :) https://github.com/philipl/pifs

Re: The $5000 Compression Challenge

#85

Post by davmre »

function_seven wrote: post #80
davmre wrote: post #48

Earlier quoted context omitted.

The "custom algorithm" thing is a red herring. You'll need to use some method to come up with your custom algorithm, once you see the input file, and whatever method you choose is itself a compression procedure, targeted at a fixed decoder which is essentially a Bash shell with a C compiler (* ). If you intend to treat different inputs differently (e.g., "if it contains the string "AB", I'll use this algorithm, if it…

> If you intend to treat different inputs differently (e.g., "if it contains the string "AB", I'll use this algorithm, if it has more zeros than ones, I'll use this other one, etc"), this just means that your compression procedure contains some 'if' statements. The laws of information theory don't care whether your compression procedure is actually a computer program or just implicitly encoded into human actions; it'…

I understand that the contestant gets to specify a "decompressor"; my point is that this is not information-theoretically relevant. The real decompressor in this challenge is the Linux/C runtime environment. The "decompression" program you send is really just part of the compressed payload, and whatever steps you, as a human, take to produce the compressed payload (encompassing both the code and data portions) are ultimately governed by information theoretic limitations.

Another way to say this is that although you have the 'privilege' of a designing a custom decompressor for this one file, this is not really a benefit since your custom decompressor counts against the space limit. (in contrast to the typical information-theoretic setting where the channel can have an arbitrary pre-specified decoder).

Re: The $5000 Compression Challenge

#86

Post by skatenerd »

mappu wrote: post #40
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).

I bet that with longer strings, the odds of drawing a kolmogorov-random string are high enough that he's guaranteed to make money from his Challenge

Re: The $5000 Compression Challenge

#87

Post by ghayes »

eridius wrote: post #83
seandougall wrote: post #77

Earlier quoted context omitted.

> completely baseless conclusion that the multiple files would be considered purely based on their file size You mean, like... > I meant can I send you a compressor and several compressed files whose total file size is less than the original uncompressed file and from which I can regenerate the original uncompressed file. (to which Mike agreed)?

Since this is still a pedantry argument: Mike agreed that Patrick could send multiple files, but Mike never agreed that these files would be accepted as a winning submission. Furthermore, Mike never agreed that the filenames of the files would be considered to be meaningful data (without contributing to the filesize calculation).

> Mike agreed that Patrick could send multiple file, but Mike never agreed that these files would be accepted as a winning submission

Then what is "agreeing"? These two sentences appear logically inconsistent.

Re: The $5000 Compression Challenge

#88

Post by caf »

eridius wrote: post #72
kazinator wrote: post #27

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

I admit I'm surprised to see this comment is still the top comment. I wrote it off when it was first written as being far too pedantic to be at all meaningful, but I guess other people are falling for the same trick. This is pure pedantry, and it's bad pedantry at that. Your argument is that Mike agreed that multiple files could be submitted, and from that you're drawing the completely baseless conclusion that the mu…

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.

Re: The $5000 Compression Challenge

#89

Post by anamexis »

caf wrote: post #88
eridius wrote: post #72

Earlier quoted context omitted.

I admit I'm surprised to see this comment is still the top comment. I wrote it off when it was first written as being far too pedantic to be at all meaningful, but I guess other people are falling for the same trick. This is pure pedantry, and it's bad pedantry at that. Your argument is that Mike agreed that multiple files could be submitted, and from that you're drawing the completely baseless conclusion that the mu…

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.

Re: The $5000 Compression Challenge

#90

Post by progrn »

Can someone explain why this is not possible? I understand why sending a decompressor beforehand is not possible for all inputs. I don't understand this formulation of the problem, where it only needs to work for one input that you get before you need to create the decompressor.
Post reply on HN