I'm confused about the challenge. Why wouldn't simply using gzip work? I must be missing something obvious.
The $5000 Compression Challenge
51–60 of 175 posts
Re: The $5000 Compression Challenge
#52Mike 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…
Nope, perfectly acceptable for Goldman to keep the $100.
Craig tried to play a game of semantics, and lost because semantics let Goldman weasel out by pointing to O/S meta data.
The challenge clearly, repeatedly, stated that Goldman would give $5000 to anyone who could compress a datafile such that the combined size of file and decompressor was smaller than the original datafile.
Craig did not compress the data stored. He split the file up into multiple smaller files and using "5" as the boundary. However, by creating 218 files, he increased the amount of space required to store this data. Ergo, the combined size of the "compressed" files and the decompressor exceeded the size of the original file. It is only by excluding the space taken up by the meta data that the "compressed" files are smaller. Furtheremore, elsewhere it was noted that: "The FAQ clearly outlines that filesystem exploits are not true compression."
Re: The $5000 Compression Challenge
#53Can't he just send you a Kolmogorov-random file? The definition of randomness (in Kolmogorov sense) basically corresponds directly to his challenge. Also, Kolmogorov-random sequences vastly outnumber non-random sequences in general, so with a long-enough file, I wonder how certain he can be that he has generated such a file. http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...
Read the article, this is a circumvention rather than compression, although if you define Komogorov-randomness appropriately, such a definition would work.
But modern OS's have non-determinism available: take a Kolmogorov-random file of size n which can be generated by a program n+1. Then, replace a certain part of the program (totaling k bits, and delete 2 extra bits) with a function drawing k+2 random bits from the OS. Then with probability 2^-(k+2), you win.
Re: The $5000 Compression Challenge
#54Earlier quoted context omitted.
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 exis…
> finding a third party with domain expertise, whom they both trust
I would say that in this specific instance, they could've quite easily agreed on a reputable user from the comp.compression newsgroup whom they both trust.
> adjudicate at very low cost.
It makes sense that arbitrators for niche markets with considerable domain expertise could charge a premium for their services. Say, $50-$150 for that specific case doesn't seem like a stretch.
Also, note that the fee could be charged only in case of dispute. (and indeed, many trust agents on Bitrated offer their services for free or nearly-free when there's no dispute and no work on their part. 0.1% base fee + 2% for disputes seems to be a popular fee structure.)
> Establishing trust between strangers is a very hard problem.
Indeed! This is the main problem we're trying to tackle, which is arguably much harder than providing the technological platform for payments.
> And while you may find a way to innovate around existing laws, new laws will be written.
The thing is, we aren't taking advantage of some "loophole" or anything like that. The escrow regulations exists for a reason and makes a lot of sense - holding funds on behalf of others should have strict regulations attached to it. Escrow providers are trusted to keep the funds safe from thieves, not to "run away" with them, and to resist the temptation to invest user funds to make a (potentially quite high) profit while holding them (which could result in losing them, even in relatively "safe" investments).
With multi-signature, none of that risk exists, and so it makes sense that the regulation won't either. Even when new laws gets written to address that, they're likely to be much less strict.
The legal situation with multi-signature is very similar to a binding arbitration clause, so we anticipate regulations to be based off of that (and arbitration is significantly less strictly regulated than escrow).
Re: The $5000 Compression Challenge
#55I'm confused about the challenge. Why wouldn't simply using gzip work? I must be missing something obvious.
GZIP would not apply very much compression, at all, to purely random data.
So the compressed data + gzip decompressor would very likely be a greater size than the original data.
Re: The $5000 Compression Challenge
#56Earlier quoted context omitted.
The challenge was to provide a decompressor for one file, not any or all files. This proof of the impossibility of a compressor that can compress any file has been known for decades.
Actually even that is not feasible: Assume that you split a m byte string into k byte decompressor and l byte input data. If k+l sum_{i=0}^{m-1} 2^i = 2^m -1 there exists at least one string in the space of m character strings which can not be compressed by any algorithm.
Yes, knowing which string(s) to choose which have this property as the challenge giver is the hard part.
Re: The $5000 Compression Challenge
#57Earlier quoted context omitted.
The challenge was to provide a decompressor for one file, not any or all files. This proof of the impossibility of a compressor that can compress any file has been known for decades.
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.…
Sure. It's possible to win, and it's also possible to lose, depending on the specific file provided. This is much better than reformulating the problem to an impossible one (compress any file, instead of this one specific file)
Re: The $5000 Compression Challenge
#58Here'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...
Or just have the decompressor log onto a server and download the original file. Only risk then is internet connection.
Re: The $5000 Compression Challenge
#59Mike 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…
Nope, perfectly acceptable for Goldman to keep the $100. Craig tried to play a game of semantics, and lost because semantics let Goldman weasel out by pointing to O/S meta data. The challenge clearly, repeatedly, stated that Goldman would give $5000 to anyone who could compress a datafile such that the combined size of file and decompressor was smaller than the original datafile. Craig did not compress the data store…
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.
Re: The $5000 Compression Challenge
#60I'm confused about the challenge. Why wouldn't simply using gzip work? I must be missing something obvious.
If you're given perfectly random data, gzipping it will (almost) never reduce the size so much that you could fit the gunzip binary in the reduced space. In the extremely rare occurrence that the generated random data has, say, a repeated string longer than the gunzip binary, the challenger could be on guard for that and just regenerate random data until that's not the case.
To be more formal, the challenger is finding what he believes to be a string that is Kolmogorov-random, and betting (quite safely) that the challenged party can't prove him wrong.
http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...