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

181–190 of 192 posts

Re: The $5000 Compression Challenge (2001)

#181

Post by theyapper »

This compression challenge discussion raises fascinating questions about how we approach data representation. While I agree with the core information theory principles being cited, I wanted to share something relevant - US Patent 12,136,933 B2 just granted for a fascinating approach called "Kinetic Data Primers" (KDP).

Let's step back and consider a different perspective that builds on some key mathematical principles:

Every binary file, regardless of its content or randomness, can be viewed as representing one specific large number. This isn't controversial - it's just a different way of looking at the data.

Many large numbers can be expressed more efficiently using mathematical notation (e.g., 10^100 is far more compact than writing out 1 followed by 100 zeros). Furthermore, this efficiency advantage tends to increase with larger numbers.

These numerical conversions are perfectly lossless and reversible. We can go from binary to decimal and back without losing any information.

This naturally leads to some interesting questions: What happens to our usual compression impossibility proofs when we consider perfect numerical transformations rather than traditional pattern matching? Could mathematical expressions capture patterns that aren't obvious in binary form? As numbers get larger, does the potential for more efficient mathematical representation increase?

The KDP patent explores some of these ideas in depth. I'm not claiming this solves all compression challenges - but I think it highlights how fresh perspectives and mathematical approaches might reveal new ways of thinking about data representation.

Would be curious to hear others' thoughts, especially from those with expertise in number theory or information theory. How do these mathematical properties interact with our traditional understanding of compression limits?

Re: The $5000 Compression Challenge (2001)

#182

Post by ball_of_lint »

hinkley wrote: post #154
ball_of_lint wrote: post #107

This strategy or something like it legitimately wins the challenge. The challenge (based on expected value) is not to find some compression scheme that will compress 100% or even 50% of files to less than their original size. Instead it's to find any (set of) compression schemes that will compress more than 1/50 = 2% of arbitrary random files to less than their original size. You can construct such a program essentia…

No. You sound as if you’re familiar with the culture but it’s clear that you’re not. The problem with comp.compression was always that its Eternal September is new people showing up every week claiming they’ve found a universal compression algorithm that compresses everything - the perpetual motion machine of information theory. Having gotten tired of explaining to people who think they’re fighting “dogma” not the la…

I'm not familiar with the culture.

Nothing in the challenge says anything about doing universal compression. In fact the key point I'm trying to make is that you _don't_ have to make a universal compressor or break entropy to win, instead just find some scheme that makes 2% of random files shorter than the original, even if it makes 98% of files much much longer. The overall entropy is increased. I wouldn't use this for anything else. But it does beat the challenge as stated.

I'd agree that Patrick didn't follow the "spirit" of the challenge or do anything interesting with compression. But in doing this I think he made a good point, which is roughly that you need to be very careful and explicit when posing challenges like this or people are going to use your sloppy wording against you.

Re: The $5000 Compression Challenge (2001)

#183

Post by ball_of_lint »

Dylan16807 wrote: post #177
ttshaw1 wrote: post #164

Earlier quoted context omitted.

If they're trying to dissuade "universal compressors" then Mike needed to ask for the algorithm first, and then generate his file. If you tell me "I bet you can't compress this file!" then I can do whatever I want to write some stupid one-off compressor to shave a byte off and take your money.

It's a limited risk. Even if the file is compressible by one byte, it's very unlikely you can figure out how to get a decompressor functioning without plenty of bytes of overhead. And even if that problem disappears, he'd still win 99.6% of the time. And you can get rid of that risk by requiring 100 bytes of shrink. Just measure the size right.

I think it would be better to require a meaningful percentage (say 1%) of compression rather than an exact count of bytes. Especially while people can ask for arbitrarily large files.

Re: The $5000 Compression Challenge (2001)

#184

Post by spencerflem »

Retr0id wrote: post #146
spencerflem wrote: post #35

Earlier quoted context omitted.

That's how all compressors work, in that likely files (eg. ASCII, obvious patterns, etc) become smaller and unlikely files become bigger.

Right, but the point was, the case where it became bigger was ~impossible to find.

Yeah good point, kinda glossed over that part of the original post. Don't think that that's possible fwiw.

IMO. the fun part of compression algorithms is that the set of files that become smaller is as narrow as possible while the set of files that become bigger is as big as possible, so _most_ files don't compress well! The trick is to get the set of files that get smaller to be just the useful files and nothing else.

Re: The $5000 Compression Challenge (2001)

#185

Post by spott »

l33t7332273 wrote: post #51
stavros wrote: post #29

Sorry, if you're trying to hustle people by xstging $100 per try, don't catch the sleight of hand in the "multiple files" question, and accept, you were beaten at your own game, fair and square.

I feel like if the FAQ requires not using filename shenanigans then the slight of hand was illegal the whole way.

The FAQ was not part of the challenge statement. It was part of the newsgroup I believe.

Re: The $5000 Compression Challenge (2001)

#186

Post by ultimafan »

evilotto wrote: post #115

This is why we can't have nice things. Some volunteer puts in time maintaining something and makes a claim that is obviously correct and - most likely in jest - promises cash to anyone who shows it to be wrong. Then some rules lawyer decides that he's better than the unpaid volunteer and does his best to humiliate him, just for the lulz. Is it any surprise that volunteers rarely stick around for long? Nowadays lots o…

The "unpaid" volunteer in question was raking in $100 per attempt for an arguably impossible task. That unquestionably moves the situation from a bounty/prize to a gambling house taking rigged bets and it's pretty clear by his language in the emails that he took pleasure in his position. How many fools did he part from their money before getting one upped by Patrick? And how did he act when he finally realized he wasn't as clever as he thought?

I'd agree that if this was a free entry situation he'd be fully within his rights turning down trolls, rules lawyers, etc. for the same reasons you mentioned. Trying to scam a well intentioned but naive bounty post would be sad behavior. But this guy was clearly taking money on a position he never intended to pay out on and not losing any sleep over it.

Re: The $5000 Compression Challenge (2001)

#187

Post by Dylan16807 »

ball_of_lint wrote: post #183
Dylan16807 wrote: post #177

Earlier quoted context omitted.

It's a limited risk. Even if the file is compressible by one byte, it's very unlikely you can figure out how to get a decompressor functioning without plenty of bytes of overhead. And even if that problem disappears, he'd still win 99.6% of the time. And you can get rid of that risk by requiring 100 bytes of shrink. Just measure the size right.

I think it would be better to require a meaningful percentage (say 1%) of compression rather than an exact count of bytes. Especially while people can ask for arbitrarily large files.

The chance that a randomly generated 1KB file can shrink by 100 bytes is the same as the chance that a randomly generated 100MB file can shrink by 100 bytes.

And that chance is too low to distinguish from zero before the universe dies.

Re: The $5000 Compression Challenge (2001)

#188

Post by evilotto »

ultimafan wrote: post #186
evilotto wrote: post #115

This is why we can't have nice things. Some volunteer puts in time maintaining something and makes a claim that is obviously correct and - most likely in jest - promises cash to anyone who shows it to be wrong. Then some rules lawyer decides that he's better than the unpaid volunteer and does his best to humiliate him, just for the lulz. Is it any surprise that volunteers rarely stick around for long? Nowadays lots o…

The "unpaid" volunteer in question was raking in $100 per attempt for an arguably impossible task. That unquestionably moves the situation from a bounty/prize to a gambling house taking rigged bets and it's pretty clear by his language in the emails that he took pleasure in his position. How many fools did he part from their money before getting one upped by Patrick? And how did he act when he finally realized he was…

That's not what it was at all.

Any time you say that something can't be done, you will attract people who say "I have found a way to do it!" Even more so if you have a proof that it can't be done. This phenomenon is far older than the internet; the term "morbus cyclometricus" suggests its origins in antiquity.

The FAQ maintainer was not looking to profit off fools. They wanted to chase them off; after spending several pages explaining why the task is impossible it is tedious to explain to a crank (the term generally used for such people, as described by Underwood Dudley) that they are in fact wrong, the task is impossible, and here's why. It's easier to say "Pay me if you want to waste me time" and reasonably assume that no one will do it.

It's similar in spirit to the James Randi challenge. You're not going to win it, because you're not going to prove that math or science is wrong. But the JREF had as its goal to expose the charlatans, and had the time and resources to devote to the task. A newsgroup FAQ maintainer has neither the time nor the resources. So they shouldn't have volunteered? Then you have no volunteers. Hooray for the internet.

Now yes, every once in a great while someone will come along and legitimately do something that was claimed un-doable; the obvious case is George Dantzig. But that case also shows that any scientist or mathematician who can be shown an error in something thought impossible will be thrilled at the discovery, because that is new knowledge, which is the whole point. Poking a hole in the rules of the contest, finding a weasel way around them, is not something interesting at all.

Re: The $5000 Compression Challenge (2001)

#189

Post by ultimafan »

evilotto wrote: post #188
ultimafan wrote: post #186

Earlier quoted context omitted.

The "unpaid" volunteer in question was raking in $100 per attempt for an arguably impossible task. That unquestionably moves the situation from a bounty/prize to a gambling house taking rigged bets and it's pretty clear by his language in the emails that he took pleasure in his position. How many fools did he part from their money before getting one upped by Patrick? And how did he act when he finally realized he was…

That's not what it was at all. Any time you say that something can't be done, you will attract people who say "I have found a way to do it!" Even more so if you have a proof that it can't be done. This phenomenon is far older than the internet; the term "morbus cyclometricus" suggests its origins in antiquity. The FAQ maintainer was not looking to profit off fools. They wanted to chase them off; after spending severa…

Sorry, I don't buy that argument. You could just ignore such people instead of take advantage of their foolishness for monetary gain. Nothing says you have to engage with each and every person showing up with preposterous claims on the internet. If he was the actual FAQ maintainer, using his position to advertise an impossible prop bet that really would only sucker in "cranks" isn't moral behavior. Failing to pay out by weaseling your way out of it with pedantic arguments about intent is even less so.

As far as I'm aware of the James Randi challenge doesn't require a participant to pay anything- it's genuinely a challenge and not a bet. It's not taking advantage of idiots to part them from their money and gloat about it over them after.

Re: The $5000 Compression Challenge (2001)

#190

Post by hinkley »

ball_of_lint wrote: post #182
hinkley wrote: post #154

Earlier quoted context omitted.

No. You sound as if you’re familiar with the culture but it’s clear that you’re not. The problem with comp.compression was always that its Eternal September is new people showing up every week claiming they’ve found a universal compression algorithm that compresses everything - the perpetual motion machine of information theory. Having gotten tired of explaining to people who think they’re fighting “dogma” not the la…

I'm not familiar with the culture. Nothing in the challenge says anything about doing universal compression. In fact the key point I'm trying to make is that you _don't_ have to make a universal compressor or break entropy to win, instead just find some scheme that makes 2% of random files shorter than the original, even if it makes 98% of files much much longer. The overall entropy is increased. I wouldn't use this…

> Nothing in the challenge says anything about doing universal compression

Because it’s out of context. It also makes the winner seem more sympathetic, which is why it’s not accident it’s not provided. It’s the Missing, Missing Reason.

Post reply on HN