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

151–160 of 175 posts

Re: The $5000 Compression Challenge

#151

Post by pgaddict »

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 that's pretty much what he says in his post to comp.compression, where he announces that someone accepted the challenge. Let me quote:

> Before naming the individual and giving additional details of our > correspondence, I would like to give him some time to analyze the > data I will be sending him. It would be very easy to point out to > him the impossibility of his task, but far more interesting to see > how long he will struggle with the problem before realizing it for > himself. > > I am supposing that one of his fellow co-workers probably referred > him to my challenge, as I cannot fathom that someone would read the > comp.compression faq first and then want to participate after > understanding the futility of the effort. On the other hand, some > people just don't understand information theory too well. > > I'll try to give him a complete explanation of his error after a > week or so, I guess. :)

So Mike is just smug about how clever he is, how stupid the other person is, not even suspecting there might be a loophole in the challenge.

I see no sign of interest in learning what the other person is up to, or even admitting that there might be something to learn.

Re: The $5000 Compression Challenge

#152

Post by compbio »

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

> If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file? Maybe because the file was XOR'd with a secret one time pad?

Blast! That would require our solution to break all known encryption. Then it would be easier to just target Goldman's setup.

A file with output from AES-256("sekrit") would not be random to Goldman. It would appear random to us, until we crack it with a plausible password. Key to randomness is unpredictability. The moment Goldman saves some atmospheric noise on his computer and makes a short pointer to it on his filesystem, is the moment this file loses its claimed unpredictability. Goldman knows this file deeply: He himself has compressed meaningless random data into predictable information that has meaning and purpose, a feat he set out to prove impossible. By simply entering the challenge with real meaningless randomness you make Goldman solve it for you.

Re: The $5000 Compression Challenge

#153

Post by compbio »

jakobegger wrote: post #111
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.)

Yes, if you want to be sure that your solution is correct, you must run the compressor yourself. Then you count the number of collisions it takes to happen upon the correct solution and feed this counter to your decompressor. But then you place the burden of solving the halting problem on yourself and then you got more serious problems than compressing random data.

Re: The $5000 Compression Challenge

#154

Post by bo1024 »

leni536 wrote: post #144
bo1024 wrote: post #127

Earlier quoted context omitted.

> Randomness is not a property of a single file. You can't look at a byte sequence and say that "it's random". Interestingly, this is less true than you might think. The mathematics of Kolmogorov complexity[1] formalizes the idea that a given finite fixed string is "random". In this framework, you can have a byte sequence that definitely is random. (However, your second sentence I quoted is still technically true her…

>The mathematics of Kolmogorov complexity[1] formalizes the idea that a given finite fixed string is "random". I read into the wiki article and this approach is certainly interesting. However this complexity depends on the description language so there is no unique way to determine if a string is random.

Right. However, the idea is for any two ways (say Java and Haskell), there will be a constant so that they will agree on all strings up to a constant. So it's quite robust and seems to capture something fundamental or deep about randomness and information...

Re: The $5000 Compression Challenge

#156

Post by titanomachy »

brownbat wrote: post #146
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. If you then complain that THAT is cheating, you're a pedantic idiot I feel the same way when casinos bust card counters. You use math to take money from suckers. When other people use your rules and better math to take money from you, that's suddenly deeply immoral.

I don't think anyone feels that card-counting is deeply immoral. It's more like, "we lose money when people do this, so we will do everything in our power to prevent it."

Re: The $5000 Compression Challenge

#157

Post by emn13 »

DougBTX wrote: post #137
emn13 wrote: post #126

Earlier quoted context omitted.

Mike's responses could have been better, but in the correspondence I see no guarantee that the files will be presented in order, or with the same file names, or in an otherwise empty directory. That sounds close to cheating, but I think it's exactly in the spirit of both the original challenge by Mike and the response by Patrick. After all, the original challenge didn't mention multiple files (so it's not surprising…

The "compressed" files includes a header file which records the original file name and the number of parts which make up the compressed file, so it doesn't depend on directory listing to re-combine the parts.

Yes, it does. It records the original file name, not the name of the parts, and it needs the names+metadata of those parts (specifically in this case their order) to reconstruct the original file.

Re: The $5000 Compression Challenge

#158

Post by emn13 »

oneeyedpigeon wrote: post #133
emn13 wrote: post #129

Earlier quoted context omitted.

But that's not what happened. Patrick , not Mike, changed the rules, and he intentionally introduced a loophole. But in doing so, he failed to specify that file names were to be left unaltered. I think it's fair that if you make intentionally tricky rules, you not be surprised when your own loopholes are exploited. Providing multiple files with the (deceptive) intention of storing data via filesystem metadata, but th…

This is exactly why such challenges are always entirely unsatisfactory and nothing but a pointless distraction. There might be some point in providing entertainment to both parties if the pedantry war weren't entered into, but the nature of the challenge all but guarantees that will happen. Mike will always be able to find an excuse not to pay. If Parrick had imposed the 'no file renaming' condition, Mike could have…

I'm not sure I'd go that far, but it's definitely not a surprise to see it fizzle out. It's particularly uninteresting here because a real solution is either impossible, or only possible because Mike's random source isn't entirely random (which is kinda boring).

Then again, the purpose apparently was to make crackpots put their money where their mouth is rather than spam the usegroup, so perhaps fairness isn't the best success criterium.

Re: The $5000 Compression Challenge

#159

Post by emn13 »

Dylan16807 wrote: post #136
emn13 wrote: post #128

Earlier quoted context omitted.

Note that he never guaranteed to leave the files with the same file names, and without that, Patrick's trick wouldn't have worked. Given the fact that Patrick made the rules concerning multiple files, and that they were intentionally tricky, I think it's fair to interpret them in that spirit - as a trick. Notably, even without the ordering there is still some information leakage purely in terms of file sizes, but tha…

He could have ordered the files by size pretty easily. Trick still would have worked. No fancy requirements needed. Just making the files available in any manner. And yes there needs to be a way to know which file(s) are the compressed data, that loophole would disqualify any entry.

Yep, file sizes alone leak sufficient information to be an issue, but it's a bit of a hypothetical because that's not what actually happened. Clearly, Mike shouldn't have allowed multiple files (or should have specified some kind of overhead for multiple files), and clearly there are other tricks Patrick could have used, but with these unfortunate rules and this submission nothing seems to require keeping file order intact.

It's a good point about needing to know which files are compressed. On a philosophical level, I'm not sure whether that means there actually should be a way to know which file(s) are the compressed data, or that the rules are simply broken...

Re: The $5000 Compression Challenge

#160

Post by emn13 »

kazinator wrote: post #62
okatzzz wrote: post #59

Earlier quoted context omitted.

This interpretation is inconsistent with Goldman's own statement about the original data that "the file size is 3145728". He didn't say "the file size is 3145728 plus some file system overhead", so by file size he was thinking of the number of bytes in the file ... until he was outsmarted. It's hardly a filesystem exploit if - again by Goldman's own statement - gunzip is allowable.

I suspect that if the challenge had been solved with a single file, Goldman would try to get out of paying by claiming that the program's size should include the size of the interpreter for its language, and the libraries linked to that, the size of the command line needed to invoke it (including the pointer vector and null termination), not to mention the underlying kernel ...

I don't know goldman, and I bet you don't either - but there's a pretty big difference between this solution (which clearly cheats the aim of the challenge, and a solution that actually compresses. People hate to reward cheaters, even if it's a fun kind of cheat from the outside. But that doesn't mean he wouldn't have payed out for a real solution, which likely would have been quite interesting (and not quite as impossible as it's being made out to be, since we don't know whether his random source is truly random).
Post reply on HN