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

91–100 of 175 posts

Re: The $5000 Compression Challenge

#91

Post by x0x0 »

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?

Re: The $5000 Compression Challenge

#92

Post by Intermernet »

function_seven wrote: post #82
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…

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

That's exactly what I was getting at.

If gzip was allowed, then any common decompression utility should be allowed.

If that's the case, and said utility relies on an external library, should that library be included as part of the size of the decompression utility?

It's arguable that the "fabric" over which the data is delivered shouldn't matter. If shouldn't really matter if the linked library comes from the same SSD as the executable, or from a server on the other side of the world.

We currently define "the machine" as the internals of a box. Would this count if you were running the executable from a removable drive? If not, why does "network storage" trigger the disqualification, and not "USB storage"?

I understand the original premise of Mike's challenge, but considering a loophole is being discussed here, I'd like to know where people see that the boundaries of similar loopholes lie.

Re: The $5000 Compression Challenge

#93

Post by raverbashing »

progrn wrote: post #90

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.

Some simple explanation

Compression exploits redundancy in a data stream (basically). You basically get "all symbols" (and how you define this varies according to your compression method: you could do all letters in the case of text, or even text snippets that repeat, etc) and reassemble them in a way that the ones that repeat the most take less space (and you also need to start from a basic dictionary known by all uncompressors or ship it with your compressed file)

One simple analogy is writing with abbreviations, but if you write e.g. the reader has to know what "e.g." means or you have to put in the beginning "e.g. = example" (and this also takes space)

Now, a randomly generated file ideally has all symbols repeating with the same frequency, (we say all symbols have the same entropy - I'm not sure about this exact wording), hence you can't take a symbol that repeats more or less and make it take less space in your compressed file

Re: The $5000 Compression Challenge

#94

Post by louis-paul »

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…

It's inventive, but what if instead of doing it at the byte level, we did it at the bit level? Instead of splitting files on every "5" encountered, we split them at every 1 in binary, which gives about 50% of "compression".

Re: The $5000 Compression Challenge

#95

Post by paulsecwhatt »

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 then complain that THAT is cheating, you're a pedantic idiot - one of those annoying kids in middle school who loses a bet and then tries every possible way to weasel himself out.

To add fuel to the fire, his obnoxious replies such as "I tried running the first two files and it didn't work", make my blood boil, as it's a clear attempt to try and belittle the contestant.

Re: The $5000 Compression Challenge

#96

Post by prettyrandom100 »

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.

Re: The $5000 Compression Challenge

#97

Post by function_seven »

davmre wrote: post #85
function_seven wrote: post #80

Earlier quoted context omitted.

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

Yeah, it's not a benefit, except if the challenge-giver makes a mistake and offers a file that happens to have nicely-compressible characteristics. Basically you're spending $100 on the hopes that the file you're tasked with compressing just happens to have low enough entropy that it can be successfully compressed by more than the decompressor's size.

Not a good bet to take.

> my point is that this is not information-theoretically relevant.

Exactly. This whole post is about the challenger trying to be clever with the rules and trying to sidestep the core information theory.

Re: The $5000 Compression Challenge

#98

Post by m_mueller »

compbio wrote: post #49
piannucci wrote: post #36

Earlier quoted context omitted.

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.

Chances of getting a collision is higher than getting a good solution, but having multiple hashes does help in increasing the chance at a good solution. With a hash 1 bit less than the length of the file, we put two pigeons inside one hole, and have a 50% chance at picking the right pigeon. The fewer/smaller hashes, the more we get "sorry, but no".

Also, I guess the hash algorithm could be specifically tested to work for this particular solution, couldn't it (although only after having spent the $100 of course)?. The problem I guess is to have a script that takes up less space than for the hash to still work without a collision for the particular data. Even with the smallest possible program or script, this probably isn't going to work then.

Re: The $5000 Compression Challenge

#99

Post by cplease »

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.

No it wouldn't work! Hashes do not defy information theory, they lose information. Such brute forcing would only find hash collisions and "decompress" to a different text than the original.

Re: The $5000 Compression Challenge

#100

Post by jholman »

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.

I endorse the creativity in your approach, but you are mistaken; this will not (deterministically) work.

Given a hash function that hashes an input I (of size N, comprised of N arbitrary bytes) to a digest D (of size M), then assuming that M is a fixed value, then for each output digest D_0, there will be 2^(N-M) values that hash to that D_0. How will you tell which is the "right" one?

Post reply on HN