(2001) tag?
The $5000 Compression Challenge
11–20 of 175 posts
Re: The $5000 Compression Challenge
#12"I still think I compressed the data in the original file. 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."
I don't really agree with that, given the fact that he used the information about the size of the files.
Re: The $5000 Compression Challenge
#13>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. Even without a filesystem - just sending data over the wire - you have to be able to delimit files in some way, and there's going to be overhead associated with that. Another way to think of this is that any particular volume could be viewed as a single big file. How much space in that big…
That just invites more ways of implicitly sharing and hiding data. Like, have each of 230 hosts have one part of the file. Instructions for running the program are "Go to %part1url. Download the file as `foo.1`. Go to %part2url. Download the file as `foo.2`." and so forth. That's exploiting the fact that the instructions for running the program aren't counted as part of the program size.
Re: The $5000 Compression Challenge
#14Quote from Mike:
> Rather, you simply split the file into 218 parts ending with the
> character "5" and then stripped that final character from each part. Thus the
> "decompressor" is nothing more than a reassembler,
> concatenating the parts and reappending
> the character "5" after each.
Normally you'd need a delimiter to separate those chunks, a delimiter that doesn't occur in the chunks e.g. through padding or escaping. That, in turn, increases the filesize, and now you're in trouble. What Patrick did was to use EOF as a new fresh "delimiter" that doesn't occur anywhere, and at a cost of zero bytes, no less.
Cheating, or inventive.
Re: The $5000 Compression Challenge
#15Re: The $5000 Compression Challenge
#16Earlier quoted context omitted.
From the link I posted in my other comment, a thought experiment... Yes, some random files can be compressed by a given program, but not all random files. The proof is fairly simple, once you think it through: Theorem: No program can compress without loss all files of size >= N bits, for any given integer N >= 0. Proof: Assume that the program can compress without loss all files of size >= N bits. Compress with this…
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. There's a 1/32 chance they were all zeros, in which case you win. The difficult part is encoding the decompression procedure into a program of less than five bits. :-)
Re: The $5000 Compression Challenge
#17Earlier quoted context omitted.
From the link I posted in my other comment, a thought experiment... Yes, some random files can be compressed by a given program, but not all random files. The proof is fairly simple, once you think it through: Theorem: No program can compress without loss all files of size >= N bits, for any given integer N >= 0. Proof: Assume that the program can compress without loss all files of size >= N bits. Compress with this…
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.
The problem wasn't well formulated, since it didn't clearly define what can or cannot be done to the decompresser based on knowledge of the output file.
But consider a more strongly formulated problem, where you must provide the decompresser and then a file is randomly selected to be put through it - as long as it's still a matter of compressing one particular file it is statistically possible to win (especially at $5000:$100) - The idea being that you can reinterpret data to make certain outputs cheaper while others more expensive.
Re: The $5000 Compression Challenge
#18I think Patrick sums it up quite well. Perhaps the interesting thing is imagining how this would go down 15 years later in 2015: Patrick asks if the bet is available; it is. They enter into a 2-of-3 bitcoin transaction with 3rd-party escrow. Patrick and Mike sign the terms (probably written in pseudocode or python) using their sending bitcoin addresses (or GPG keys). Filesharing is an order-of-magnitude easier than s…
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 risk, I guess. this might go under the radar for small things like that, but doesn't really work at scale.)
Bitcoin improves on that by not requiring a trust account - their trusted third party would simply hold one key in a 2-of-3 multi-signature scheme, giving him the authority to resolve disputes and adjudicate between them, but without holding any funds under his full control.
I find the legal implications of Bitcoin smart contracts very exciting - this significantly lowers the entry barriers for providing many kinds of financial services and opens up these markets for competition in a way that was simply impossible before. There's lots of room for innovation and disruption with that.
Disclaimer: standard IANAL/TINLA apply, but I'm the founder at a startup that facilitates exactly that (https://www.bitrated.com/) and received extensive legal guidance on the matter.
Re: The $5000 Compression Challenge
#19My money is on Hooli winning this one.
Re: The $5000 Compression Challenge
#20I think Patrick sums it up quite well. Perhaps the interesting thing is imagining how this would go down 15 years later in 2015: Patrick asks if the bet is available; it is. They enter into a 2-of-3 bitcoin transaction with 3rd-party escrow. Patrick and Mike sign the terms (probably written in pseudocode or python) using their sending bitcoin addresses (or GPG keys). Filesharing is an order-of-magnitude easier than s…
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.
The greeks could have kickstarted the industrial revolution early if they'd used hero's engine. They just didn't think about the world in that way at that time.