5 ms·

A trick similar to the recursive Barf compressor (add information to the filename). http://mattmahoney.net/dc/barf.html http://mattmahoney.net/dc/barf.html A l

by compbio 12y ago

A trick similar to the recursive Barf compressor (add information to the filename). http://mattmahoney.net/dc/barf.html http://mattmahoney.net/dc/barf.html A longer running challenge is http://www.drdobbs.com/architecture-and-design/the-enduring-challenge-of-compressing-ra/240049914 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/ 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.

function_seven 12y ago
> 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?
- compbio 12y ago
  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.
coldtea 12y ago
>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...
bo1024 12y ago
> A longer running challenge is http://www.drdobbs.com/architecture-and-design/the-enduring-.. 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).
- emn13 12y ago
  That was explicitly forbidden :-)
leni536 12y ago
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 http://ansuz.sooke.bc.ca/entry/23
- bo1024 12y ago
  > 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 http://en.wikipedia.org/wiki/Kolmogorov_complexity
  - leni536 12y ago
    >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.
    - bo1024 12y ago
jakobegger 12y ago
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.)
- compbio 12y ago
  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.
  - jakobegger 12y ago
    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.
DanBC 12y ago
> Why does he want exactly his own random file? He's running a model and needs to use the same random data each time.
- compbio 12y ago
  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.
  - DanBC 12y ago
    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.

by compbio 12y ago

function_seven 12y ago

> 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?

compbio 12y ago
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.

coldtea 12y ago

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

bo1024 12y ago

> A longer running challenge is http://www.drdobbs.com/architecture-and-design/the-enduring-.. 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).

emn13 12y ago
That was explicitly forbidden :-)

leni536 12y ago

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 http://ansuz.sooke.bc.ca/entry/23

bo1024 12y ago
> 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 http://en.wikipedia.org/wiki/Kolmogorov_complexity
- leni536 12y ago
  >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.
  - bo1024 12y ago

jakobegger 12y ago

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

compbio 12y ago
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.
- jakobegger 12y ago
  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.

DanBC 12y ago

> Why does he want exactly his own random file? He's running a model and needs to use the same random data each time.

compbio 12y ago
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.
- DanBC 12y ago
  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.