Mike supports $SPORT team the Compressors. He's so sure they are unbeatable that he accepts 50:1 bets against them. Patrick bets 100$ that they won't win this year's championship; Mike accepts. Later, the Compressors announce financial troubles and can't pay the fee to enter the championship, which is then won by another team. Patrick reclaims his 5000$. Mike refuses to pay saying that the Compressors have not been b…
And the FAQ for the bet said that if a team can’t afford to enter the playoffs then the bet is off.
:shocked_pikachu: Renegadry aside, for those who are more interested in the Information Theory perspective on this: Kolmogorov complexity is a good teaching tool, but hardly used in engineering practice because it contains serious foot-guns. One example of defining K complexity(S, M) is the length of the shortest initial tape contents P for a given abstract machine M such that, when M is started on this tape, the mac…
>uniform random strings’ K complexity is only _tightly concentrated around_ the strings’ length plus a machine-dependent constant
What is the distribution of the complexity of a string? Is there some Chernof-like bound?
I'm rather skeptical of this claim that the data was compressed in 2018 because there is no further information, apart from a hash value given. If it's a true claim they must have identified some "non-random" aspect of the original data, and then they could have given more info.
Not necessarily. Consider a big file of random uniformly distributed bytes. It's easy to show that in practice some bytes are more common than others (because random), and that necessarily therefore the expected spacing between those specific bytes is less than 256, which gives you a small fraction of a bit you can save in a recoding of those specific bytes (distance from last byte of a specific value). With a big en…
>It's easy to show that in practice some bytes are more common than others (because random)
I don’t follow. Wouldn’t that be (because not random)
Story time. In our Data Structures and Algorithms class during my undergrad, we had a similar challenge posed to us by an associate professor who was quite proud of the fact that it had never been beaten. The sophistication of my compression understanding at the time extended to lempel-ziv and huffman and well... that's about it. So I was like, “Okay, I’m not going to create the world’s best compression method on a w…
Come on dude, great story, missing ending! Fill us in please.
I’d take this bet. > With this offer, you can tune your algorithm to my data. One can generate a 1GB file or 10GB file. It is highly likely that there is some form of a repeatable pattern in there to shave off 50-100 bytes by sliding window search. Then the decompressor is essentially - at this index, expand this pattern. The compressed file excludes the range of pattern. One may not always get such a pattern, but on…
The whole point is Mike had control over creating the source file, and so obviously checked for random repeating patterns and removed them before giving the file to the challenger.
On top of this, it takes more data to store the address of the repeating byte pattern than the original pattern does. Therefore you are creating more data than you are saving.
If it was this easy then hundreds of people would have taken on the challenge and won the £5k.
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.
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.
You could do the same spitting trick but only split at progressively increasing file lengths at the character '5'. The "compression" would be worse, so you'd need a larger starting file, but you could still satisfy the requirements this way and be independent of the filenames. The decompressor would just sort the files by increasing length before merging.
Nice idea, but doesn't this require a linear increase of the length of the partial files and a quadratic size of the original file? If the length of a file is X, then in the next file you must skip the first X characters and look for a "5" that in average is in the X+128 position. So the average length of the Nth file is 128*N and if you want to reduce C bytes the size of the original file should be ~128 C^2/2 (inste…
Yes, I think it is quadratic. I don't claim it's practical (the original isn't practical either though), but just that the dependency on filenames isn't fundamental.
I have a fundamental problem with the Hutter prize stating that intelligence is related to compression & then sponsoring a prize for lossless compression. Intelligence is related to lossy compression. Lossless is mainly a mechanistic act.
Isn’t the intelligence shown by compressing lossless the scheme you use? Applying the algorithm is the easy part, the proof of intelligence is inventing the algorithm which compresses.
Yes, you are proving intelligence if you invent the algorithm which compresses. If the prize was for inventing an algorithm that could then build the lossless compression scheme itself then you'd be onto something. But the prize is for the human who invents the better compression algorithm and proof of intelligence of the human would be self-evident.
Not necessarily. Consider a big file of random uniformly distributed bytes. It's easy to show that in practice some bytes are more common than others (because random), and that necessarily therefore the expected spacing between those specific bytes is less than 256, which gives you a small fraction of a bit you can save in a recoding of those specific bytes (distance from last byte of a specific value). With a big en…
>It's easy to show that in practice some bytes are more common than others (because random) I don’t follow. Wouldn’t that be (because not random)
If you generate a billion bytes using a random byte generator, and bin the resultant array into 256 bins, it will not be perfectly flat. You can use that non-flatness to encode your bits more efficiently. I suspect just using codes to do it won't work well because the bin values are so close so you'll struggle to get codes that are efficient enough, but I suspect you can use the second order difference-between-specific byte as the encoded value. That has a much more pronounced distribution heavily weighted to small values.
When implementing a PRNG, you can make its seed as big as you want. There is no mathematical law that dictates or limits the size of a seed.
I mean sure you could in theory, but in practice that's not how common built-in random number generators work. I was responding to: > chances are the length of the seed is equal to the length of the original file And why would the chances be that? You'd really have to go out of your way for that. I don't even know if there are libraries that can handle a seed and state length on the scale of megabytes. No, chances ar…
A PRNG with a 32 bit seed can only generate up to 2^32 different sequences of 32bit numbers, which are guaranteed to repeat after 2^32 generated numbers. Without doing the math, Even for a 3mb file chances are very slim there'll be a seed that generates the entire file. The number of unique 3mb files is astronomically larger than the number of sequences you can generate, even if you'd try every possible substring of all the sequences. So you need a PRNG that can generate more sequences, which you can only achieve by making the seed larger. What the person you were replying to was implying is that the size of the seed might approach the size of the sequence you're trying to generate.