The $5000 Compression Challenge • Hacker News Board

Re: The $5000 Compression Challenge

#41

Post by scintill76 » Sun, Mar 08, 2015, 3:45 AM UTC

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…

> He didn't say "okay, but there will be a 256 byte size penalty per additional file", he just plainly agreed.

Exactly. IMO the challenge-setter is the one being more unfair here, since his metadata-based reason to reject the solution applies to submissions made under the original rules too. He accepted an amendment without counter-amending to cover that loophole, so if he stands by his word, he has to pay up.

It casts doubt on whether he would pay if somebody won by the original rules with some luck. Maybe he has an implicit allowance, that merely two files can't "encode" a big enough advantage, but again, then it's his fault for not addressing that in the new rules.

Re: The $5000 Compression Challenge

#42

Post by snowwrestler » Sun, Mar 08, 2015, 3:47 AM UTC

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 understand their area of expertise as well as they do. They get angry and offended at naive questions, and seek to punish the idiots. This is a great way to take an interesting subject and ruin it for everyone.

One of the best aspects of the HN culture is that experts here tend to incline more toward teaching and less toward chastising. It's a nice change from Usenet.

Re: The $5000 Compression Challenge

#43

Post by davmre » Sun, Mar 08, 2015, 3:47 AM UTC

phamilton wrote: post #39

davmre wrote: post #16

Earlier quoted context omitted.

Yes, but you don't get to see the file until after you've sent in the $100. So in order for this to be a good bet, you'd need a method that can compress a random file with at least 2% ($100/5000) probability. That's still quite difficult. An example of an algorithm that does compress 2% (actually 1/32 ~= 3%) of random files: just drop the initial five bits of the file, and replace them with zeros upon decompression.…

Continuing that logic: You could get 6% if you can also do the same on the end of the file. There's a 1 in 16 chance that any random sequence of data will start or end with 5 zeros. The same trick could be done for 1s to bring it up to 12%. In other words, 12% of sequences will either begin or end with 5 ones or 5 zeros. Since you can inspect the data before writing the decompressor, if we can figure out how to pad t…

Unfortunately you're confusing bits and bytes (I did the same thing too at first). Fitting a decompressor in five bits is a lot harder. :-)

Re: The $5000 Compression Challenge

#44

Post by phamilton » Sun, Mar 08, 2015, 3:51 AM UTC

phamilton wrote: post #39

davmre wrote: post #16

Earlier quoted context omitted.

Yes, but you don't get to see the file until after you've sent in the $100. So in order for this to be a good bet, you'd need a method that can compress a random file with at least 2% ($100/5000) probability. That's still quite difficult. An example of an algorithm that does compress 2% (actually 1/32 ~= 3%) of random files: just drop the initial five bits of the file, and replace them with zeros upon decompression.…

Continuing that logic: You could get 6% if you can also do the same on the end of the file. There's a 1 in 16 chance that any random sequence of data will start or end with 5 zeros. The same trick could be done for 1s to bring it up to 12%. In other words, 12% of sequences will either begin or end with 5 ones or 5 zeros. Since you can inspect the data before writing the decompressor, if we can figure out how to pad t…

as pointed out... bits vs bytes... I think the overall idea here is interesting. It is "cheating" because the implicit "EOF" and "start of file" allow us to forego indexing the data. This "cheat" is similar to the technique used in the article.

Similar cheats would be to leverage hardware instructions (imagine if x86 had a "pad with N zeros" instruction that fit in 7 bits). That's still cheating because the information is hiding in the architecture.

Re: The $5000 Compression Challenge

#45

Post by a_e_k » Sun, Mar 08, 2015, 4:01 AM UTC

im3w1l wrote: post #6

I don't think it is 100% foolproof, even if no filesystem trickery is used. The random number generator used is likely not perfect and so the data should be compressible. I mean it would probably be quite difficult, but maybe possible.

From random.org, used as a source for the data:

> RANDOM.ORG offers true random numbers to anyone on the Internet. The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs.

Re: The $5000 Compression Challenge

#46

Post by leereeves » Sun, Mar 08, 2015, 4:14 AM UTC

nadaviv wrote: post #18

qopp wrote: post #4

Earlier quoted context omitted.

They could have used an escrow service 15 years ago and the challenge terms could have been defined as a Python program since Python is 24 years old.

Getting someone with domain expertise on the matter to provide escrow is non-trivial. Escrow trust accounts are heavily regulated in most parts of the world, and require licensing, bonds and lawyers. I highly doubt they would find someone willing to go through all this. The cost for (legally) operating an escrow is probably higher than the entire bet... (he could also do this without licensing, and take on the legal…

Bitcoin makes the technical process easier but doesn't help with the hard problem (as you said): finding a third party with domain expertise, whom they both trust, who is willing to adjudicate at very low cost.

It sounds like your startup is trying to solve that and create a "Trust Marketplace". Godspeed. Establishing trust between strangers is a very hard problem.

And while you may find a way to innovate around existing laws, new laws will be written.

Re: The $5000 Compression Challenge

#47

Post by im3w1l » Sun, Mar 08, 2015, 4:17 AM UTC

a_e_k wrote: post #45

im3w1l wrote: post #6

I don't think it is 100% foolproof, even if no filesystem trickery is used. The random number generator used is likely not perfect and so the data should be compressible. I mean it would probably be quite difficult, but maybe possible.

From random.org, used as a source for the data: > RANDOM.ORG offers true random numbers to anyone on the Internet. The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs.

Ah missed that. Yeah then it may be good enough randomness.

Re: The $5000 Compression Challenge

#48

Post by davmre » Sun, Mar 08, 2015, 4:19 AM UTC

martinko wrote: post #31

davmre wrote: post #16

Earlier quoted context omitted.

Yes, but you don't get to see the file until after you've sent in the $100. So in order for this to be a good bet, you'd need a method that can compress a random file with at least 2% ($100/5000) probability. That's still quite difficult. An example of an algorithm that does compress 2% (actually 1/32 ~= 3%) of random files: just drop the initial five bits of the file, and replace them with zeros upon decompression.…

>you'd need a method that can compress a random file with at least 2% ($100/5000) probability No, you'd need to be able to create a custom algo for that file with that probability. Quite a difference.

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 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's still impossible to reliably represent random data with fewer than the usual number of bits.

(* ) There's a little bit of leeway here because the challenge as stated isn't actually precise about the execution environment. You could probably sneak in a small number of illicit bits by negotiating out-of-band whether the decompressor is to be a C program, ELF binary, Perl script, etc. It's not obvious how to make this useful though.

Re: The $5000 Compression Challenge

#49

Post by compbio » Sun, Mar 08, 2015, 4:28 AM UTC

piannucci wrote: post #36

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.

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".

Re: The $5000 Compression Challenge

#50

Post by phkahler » Sun, Mar 08, 2015, 4:28 AM UTC

Here's a more risky solution. Chose an arbitrary large file size. Have the decompressor search the local file system for a file of that specific size and make a copy of it as output. This presumes he's going to have the uncompressed file on the system to verify the output of the decompressor. That may turn out to be a false assumption, but what if...