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

The $5000 Compression Challenge (2001)

patrickcraig.co.uk

Post reply on HN
Print view View original

21–30 of 192 posts

Re: The $5000 Compression Challenge (2001)

#21

Post by changoplatanero »

kittoes wrote: post #20
ccleve wrote: post #9

I wonder if it would have been possible to win the challenge legitimately? If a randomly-generated file happened to contain some redundancy through sheer chance, you could hand-craft a compressor to take advantage of it. This compressor would not work in general for random data, but it could work for this one particular case. It's a bet worth taking, because the payoff, 50:1 ($5,000 to $100), is pretty good. Play the…

What if we didn't even attempt to compress the file? Theoretically, there is a random number generator + seed combination that would output the same bytes as the source file.

Neat idea but chances are the length of the seed is equal to the length of the original file.

Re: The $5000 Compression Challenge (2001)

#22

Post by stavros »

fxtentacle wrote: post #5

This guy clearly failed because he didn't actually do any compression, he just ab-used the filesystem to store parts of the data and then tried to argue that metadata was not data... But FYI someone else actually managed to compress that exact same data: https://jasp.net/tjnn/2018/1.xhtml

If Mike didn't want multiple files, he should have said no to multiple files. The fact that he wanted $100 per try shows that he just got outhustled at his own hustle. He should have been more particular about the rules, and upheld the ones he himself set.

Re: The $5000 Compression Challenge (2001)

#24

Post by cortesoft »

benchmarkist wrote: post #15

Take random bytes from /dev/urandom, encrypt it. There is no way any compressor can reduce the size of that file. I'm pretty sure there is no way the second player can win this game. Actually, the encryption part isn't even necessary. There is no compressor that can reduce the size of a random stream of bytes.

There is no general purpose compressor that can achieve compression on all random streams of bytes... but there is a possibility to compress a specific random stream of bytes, if you get lucky

Re: The $5000 Compression Challenge (2001)

#25

Post by Retr0id »

ccleve wrote: post #9

I wonder if it would have been possible to win the challenge legitimately? If a randomly-generated file happened to contain some redundancy through sheer chance, you could hand-craft a compressor to take advantage of it. This compressor would not work in general for random data, but it could work for this one particular case. It's a bet worth taking, because the payoff, 50:1 ($5,000 to $100), is pretty good. Play the…

Somewhere (discussed on HN) someone devised a "better-than-perfect" compressor. Most inputs get compressed (smaller than input), except for one input that does not. That one input is cryptographically impossible to find - or something along those lines.

Unfortunately I can't find the article I'm describing here, maybe someone else can? It was a long time ago so I might be misrepresenting it slightly.

Re: The $5000 Compression Challenge (2001)

#26

Post by Retric »

benchmarkist wrote: post #15

Take random bytes from /dev/urandom, encrypt it. There is no way any compressor can reduce the size of that file. I'm pretty sure there is no way the second player can win this game. Actually, the encryption part isn't even necessary. There is no compressor that can reduce the size of a random stream of bytes.

But you don’t need to compress every possible file to make playing such a game a good idea.

Suppose if you shave 1 bit off of a sample bit stream you win and you lose if that fails. Your compressor looks at the first 2 bits and if it starts 11 it starts with 1 and otherwise it starts 0 then the bit stream. Now you have a 1 in 4 chance to compress a random string by 1 bit and. A 3 in 4 chance of making it longer by 1 bit.

It’s ultimately not about compression but what odds are worth it.

Re: The $5000 Compression Challenge (2001)

#27

Post by stavros »

Supermancho wrote: post #4

> It's not my fault that a file system uses up more space storing the same amount of data in two files rather than a single file. It's not interesting to see people play word games with each other in the HN comments, so why is it interesting to see this kind of disingenuous behavior? Trolls have always existed. I don't get what's interesting about it.

As Patrick said, if he had gotten a 1000-byte file and sent a 999-byte file/decompressor file back, nobody would have counted the inode data as a part of the solution. Why count it now?

Re: The $5000 Compression Challenge (2001)

#28

Post by lambdaone »

dmurray wrote: post #14
ccleve wrote: post #9

I wonder if it would have been possible to win the challenge legitimately? If a randomly-generated file happened to contain some redundancy through sheer chance, you could hand-craft a compressor to take advantage of it. This compressor would not work in general for random data, but it could work for this one particular case. It's a bet worth taking, because the payoff, 50:1 ($5,000 to $100), is pretty good. Play the…

I think you can make some argument about why this isn't possible at 50:1 odds. A plausible "decompressor" is at least, say, 30 or 100 bytes, so the random file needs to have 30 bytes less entropy than you expected, which happens with probability X where X This argument could do with more rigor, but I think it's correct. Give me 100 million to 1 odds, though, and I'll take my chances trying to brute force a compressor…

This is actually an extremely interesting question. 'Weak' files that are more easily compressable than others certainly exist, but with low probability.

For example, the all-zeros file is a member of the set of all random 3 megabyte files, and it would certainly be possible to compress that, if by great good fortune you were lucky enough to receive it - albeit something that is unlikely to ever happen in the possible lifetime of the universe, given current physical theories.

Is it possible to quantify this idea of a 'weak' file more accurately?

Re: The $5000 Compression Challenge (2001)

#30

Post by lambdaone »

cortesoft wrote: post #24
benchmarkist wrote: post #15

Take random bytes from /dev/urandom, encrypt it. There is no way any compressor can reduce the size of that file. I'm pretty sure there is no way the second player can win this game. Actually, the encryption part isn't even necessary. There is no compressor that can reduce the size of a random stream of bytes.

There is no general purpose compressor that can achieve compression on all random streams of bytes... but there is a possibility to compress a specific random stream of bytes, if you get lucky

Absolutely! Can this probability be quantified?
Post reply on HN