News for hackers. Stuff that matters.
Re:The $5000 Compression Challenge by compbio on Saturday March 07, 2015 @10:09PM (#9164344)
A trick similar to the recursive Barf compressor (add information to the filename). http://mattmahoney.net/dc/barf.html

A longer running challenge is http://www.drdobbs.com/architecture-and-design/the-enduring-... No entry fee, $100 prize, and just as unfair.

A completely serious compression challenge with serious consequences for AI and NLP: http://prize.hutter1.net/ up to 50.000$ prize money, but severe restrictions on memory and running time.

You can not beat Goldman's troll-ish challenge (certainly if the rules are retro-actively clarified in favor of the organizer). You could however try to put the challenge in limbo by creating a decompressor which bruteforces a solution, 'till some hashes match or the final heat death of the universe or the halting problem is solved, whichever comes first. Goldman will not be able to ever verify your solution, and when he does (theoretically it is not impossible), it means you win.

Or, instead of above Schrödinger's Compressor you can send a good random number generator back as your solution. If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file? Why does he want to do a diff between two random files, is he perhaps looking for order where there is none? But that's the same foolishness he accuses his participants of.

Re:The $5000 Compression Challenge by bo1024 on Sunday March 08, 2015 @01:58AM (#9164862)
> A longer running challenge is http://www.drdobbs.com/architecture-and-design/the-enduring-.... No entry fee, $100 prize, and just as unfair.

At the 10-year scale, a whole new set of tricks opens up. Invent a sufficiently popular programming language, or contribute a lot to the linux kernel, and start surreptitiously hiding bits of the file on his OS (the easiest would be for you language to have a builtin function that spits out a small part of the file).

Re:The $5000 Compression Challenge by emn13 on Sunday March 08, 2015 @08:38AM (#9165393)
That was explicitly forbidden :-)
Re:The $5000 Compression Challenge by jakobegger on Sunday March 08, 2015 @05:52AM (#9165159)
Bruteforcing a solution until hashes match doesn't work. If you try to bruteforce X bits and use a hash of size Y for validation, you will get 2^(X-Y) possible solutions.

(I made the same mistake some time ago when I tried to bruteforce a 4 byte RC4 key with 3 known bytes in the plain text; I found 256 solutions.)

Re:The $5000 Compression Challenge by compbio on Sunday March 08, 2015 @01:30PM (#9166295)
Yes, if you want to be sure that your solution is correct, you must run the compressor yourself. Then you count the number of collisions it takes to happen upon the correct solution and feed this counter to your decompressor. But then you place the burden of solving the halting problem on yourself and then you got more serious problems than compressing random data.
Re:The $5000 Compression Challenge by jakobegger on Monday March 09, 2015 @06:51AM (#9170226)
But your counter will need (X-Y) bits of storage, so you'll need to store Y + (X-Y) bits, or a total of X bits, and you have saved nothing.
Re:The $5000 Compression Challenge by leni536 on Sunday March 08, 2015 @05:40AM (#9165139)
If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file?

There is no such thing as random file. Randomness is not a property of a single file. You can't look at a byte sequence and say that "it's random". It can be random looking, you can run some statistic analysis on the byte sequence and say "It's probably generated by some good random algorithm", but even here "probably" doesn't mean any probability in [0,1].

Also there are cases in practice where you expect back the same random byte sequences even if they are randomly generated. Think about public key authentication and symmetric session key's exchange.

Randomness can be tied to the algorithm which generates a byte sequence. This information is not stored in the file in any way, it's just the mere result of an algorithm. Randomness is the "color of the bits" [1].

[1] http://ansuz.sooke.bc.ca/entry/23

Re:The $5000 Compression Challenge by bo1024 on Sunday March 08, 2015 @07:55AM (#9165303)
> Randomness is not a property of a single file. You can't look at a byte sequence and say that "it's random".

Interestingly, this is less true than you might think. The mathematics of Kolmogorov complexity[1] formalizes the idea that a given finite fixed string is "random". In this framework, you can have a byte sequence that definitely is random. (However, your second sentence I quoted is still technically true here as well because it is algorithmically undecidable how random the string is.)

(In fact one of the definitions of a random string is one that is incompressible, i.e. there is no algorithm with shorter description than the string that produces the string.)

[1] http://en.wikipedia.org/wiki/Kolmogorov_complexity

Re:The $5000 Compression Challenge by leni536 on Sunday March 08, 2015 @11:31AM (#9165865)
>The mathematics of Kolmogorov complexity[1] formalizes the idea that a given finite fixed string is "random".

I read into the wiki article and this approach is certainly interesting. However this complexity depends on the description language so there is no unique way to determine if a string is random.

Re:The $5000 Compression Challenge by bo1024 on Sunday March 08, 2015 @01:50PM (#9166377)
Right. However, the idea is for any two ways (say Java and Haskell), there will be a constant so that they will agree on all strings up to a constant. So it's quite robust and seems to capture something fundamental or deep about randomness and information...
Re:The $5000 Compression Challenge by function_seven on Sunday March 08, 2015 @01:40AM (#9164828)
> If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file?

Maybe because the file was XOR'd with a secret one time pad?

Re:The $5000 Compression Challenge by compbio on Sunday March 08, 2015 @01:17PM (#9166254)
Blast! That would require our solution to break all known encryption. Then it would be easier to just target Goldman's setup.

A file with output from AES-256("sekrit") would not be random to Goldman. It would appear random to us, until we crack it with a plausible password. Key to randomness is unpredictability. The moment Goldman saves some atmospheric noise on his computer and makes a short pointer to it on his filesystem, is the moment this file loses its claimed unpredictability. Goldman knows this file deeply: He himself has compressed meaningless random data into predictable information that has meaning and purpose, a feat he set out to prove impossible. By simply entering the challenge with real meaningless randomness you make Goldman solve it for you.

Re:The $5000 Compression Challenge by DanBC on Sunday March 08, 2015 @06:37AM (#9165215)
> Why does he want exactly his own random file?

He's running a model and needs to use the same random data each time.

Re:The $5000 Compression Challenge by compbio on Sunday March 08, 2015 @04:44PM (#9167164)
Then he can wait for the RNG to produce this same random data. Eventually it will produce a file which matches. A dynamic solution of sorts, because he would have to be quick to diff, before the file starts changing again.

I feel that the compressor for a true random stream is a true random generator. If I quickly show you a screen of black-and-white unpredictable noise, and ask you what it was, you'd compress/understand/recall that as "generate_noise()". I do not feel that this is lossy compression, for what did you lose? The ordering of a random file? Random files have no order to lose.

Re:The $5000 Compression Challenge by DanBC on Monday March 09, 2015 @05:41AM (#9170034)
When you're running a reproducible science experiment it's probably a good idea to include the actual data. For random noose this could be the generator and seed and then some good hashes but only if the experimentor used a generator and seed - if the experimentor just grabs noise from somewhere and uses that you want the actual data as part of reproducibility.
Re:The $5000 Compression Challenge by coldtea on Sunday March 08, 2015 @01:48AM (#9164844)
>If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file?

Because not all random files are equally random? DUH! He had to ensure there's no bias in the distrubution, use a good random generation, check for skewed data etc...